病毒侵袭持续中 HDU

病毒侵袭持续中

题意：统计长串中各短串出现的次数。
唯一需要注意的地方是，虽然短串只有大写英文字母，但是长串是可显示的字符，ASCII码是从32到127。
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define CLR(m,a) memset(m,a,sizeof(m))
  4 const int maxnode=1000*50+10;
  5 const int sigma=26;
  6 const int maxn=2000010;
  7 
  8 struct AC
  9 {
 10     int ch[maxnode][sigma],val[maxnode],last[maxnode],f[maxnode];
 11     int sz;
 12     int cnt[1010];  //
 13 
 14     void init()
 15     {
 16         CLR(ch[0],0);
 17         sz=1;
 18         CLR(cnt,0);
 19     }
 20 
 21     int idx(char c){return c-'A';}
 22 
 23     void inser(char *s,int v)
 24     {
 25         int u=0,n=strlen(s);
 26         for(int i=0;i<n;i++){
 27             int c=idx(s[i]);
 28             if(!ch[u][c]){
 29                 CLR(ch[sz],0);
 30                 val[sz]=0;
 31                 ch[u][c]=sz++;
 32             }
 33             u=ch[u][c];
 34         }
 35         val[u]=v;
 36     }
 37     void getfail()
 38     {
 39         queue<int> q;
 40         f[0]=0;
 41         for(int c=0;c<sigma;c++){
 42             int u=ch[0][c];
 43             if(u){
 44                 q.push(u);
 45                 f[u]=0;
 46                 last[u]=0;
 47             }
 48         }
 49         while(!q.empty()){
 50             int r=q.front();
 51             q.pop();
 52             for(int c=0;c<sigma;c++){
 53                 int u=ch[r][c];
 54                 if(!u) continue;
 55                 q.push(u);
 56                 int v=f[r];
 57                 while(v&&!ch[v][c]) v=f[v];
 58                 f[u]=ch[v][c];
 59                 last[u]=val[f[u]]?f[u]:last[f[u]];
 60             }
 61         }
 62     }
 63     void print(int u)
 64     {
 65         if(u){
 66             cnt[val[u]]++;
 67             print(last[u]);
 68         }
 69     }
 70     void query(char *s)
 71     {
 72         int u=0,n=strlen(s);
 73         for(int i=0;i<n;i++){
 74             if(!isupper(s[i])) {u=0;continue;}  //wa!!!
 75             int c=idx(s[i]);
 76             while(u&&!ch[u][c]) u=f[u];
 77             u=ch[u][c];
 78             if(val[u]) print(u);
 79             else if(last[u]) print(last[u]);
 80         }
 81     }
 82 };
 83 AC ac;
 84 int n;
 85 char s[1010][55],t[maxn];
 86 int main()
 87 {
 88     while(scanf("%d",&n)!=EOF){
 89         ac.init();
 90         for(int i=1;i<=n;i++){
 91             scanf("%s",s[i]);
 92             ac.inser(s[i],i);
 93         }
 94         ac.getfail();
 95         scanf("%s",t);
 96         ac.query(t);
 97         for(int i=1;i<=n;i++){
 98             if(ac.cnt[i]){
 99                 printf("%s: %d
",s[i],ac.cnt[i]);
100             }
101         }
102     }
103     return 0;
104 }
View Code