hdu2222

这题wa了好久，然后再discuss里看了一下，查询的字符串居然可以重复出现，也就是说
应该是2不是1。。。。感觉再也不会爱了==
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<string.h>
  4 #include<queue>
  5 using namespace std;
  6 const int maxn=10001;
  7 char tree[51],p[maxn*100];
  8 int cnt,val[maxn*50],f[maxn*50],last[maxn*50];
  9 bool vis[maxn*50];
 10 int n,top;
 11 int ch[maxn*50][26];
 12 
 13 void init()
 14 {
 15     top=1;
 16     cnt=0;
 17     memset(ch[0],0,sizeof(ch[0]));
 18     memset(val,0,sizeof(val));
 19     memset(vis,0,sizeof(vis));
 20 }
 21 
 22 void insert(char *s,int op)
 23 {
 24     int n=strlen(s);
 25     int u=0,c,i;
 26     for(i=0;i<n;i++)
 27     {
 28         c=s[i]-'a';
 29         if(ch[u][c]==0)
 30         {
 31             memset(ch[top],0,sizeof(ch[top]));
 32             val[top]=0;
 33             ch[u][c]=top++;
 34         }
 35         u=ch[u][c];
 36     }
 37     val[u]++;
 38     //printf("op=%d val=%d u=%d\n",op,val[u],u);
 39 }
 40 
 41 void getfail()
 42 {
 43     queue<int> q;
 44     int u,c;
 45     for(c=0;c<26;c++)
 46     {
 47         u=ch[0][c];
 48         if(u){f[u]=0;q.push(u);last[u]=0;}
 49     }
 50     int r,v;
 51     while(!q.empty())
 52     {
 53         r=q.front();q.pop();
 54         for(c=0;c<26;c++)
 55         {
 56             u=ch[r][c];
 57             if(!u) continue;
 58             q.push(u);
 59             v=f[r];
 60             while(v&&!ch[v][c]) v=f[v];
 61             f[u]=ch[v][c];
 62             last[u]=val[f[u]]?f[u]:last[f[u]];
 63         }
 64     }
 65 }
 66 
 67 void print(int j)
 68 {
 69     if(j)
 70     {
 71         if(!vis[j])
 72         cnt+=val[j];
 73         vis[j]=1;
 74         print(last[j]);
 75     }
 76 }
 77 void find(char *T)
 78 {
 79     int n=strlen(T),i,j=0,c;
 80     for(i=0;i<n;i++)
 81     {
 82         c=T[i]-'a';
 83         while(j&&!ch[j][c]) j=f[j];
 84         j=ch[j][c];
 85         if(val[j])  print(j);
 86         else if(last[j]) print(last[j]);
 87     }
 88 }
 89 int main()
 90 {
 91     //freopen("test.txt","r",stdin);
 92     int T;
 93     scanf("%d",&T);
 94     while(T--)
 95     {
 96         scanf("%d",&n);
 97         int i;
 98         init();
 99         for(i=0;i<n;i++)
100         {
101             scanf("%s",tree);
102             insert(tree,i+1);
103         }
104         getfail();
105         scanf("%s",p);
106         find(p);
107         printf("%d\n",cnt);
108     }
109     return 0;
110 }
View Code