HDU 5384 AC自动机

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5384

题意：给n个母串，给m个匹配串，求每个母串依次和匹配串匹配，能得到的数目和。

分析：之前并不知道AC自动机是用来求什么的，但翻模板的时候看见邝斌的字符串模板里有AC自动机一项，就看了一下，然后发现和题目要解决的问题一模一样。就开始改模板。结果没想到就是个裸的AC自动机,以为会TLE，10^10呢，迟迟不敢交，又被坑了。

目前对原理还一无所知。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <queue>
  4 using namespace std;
  5 inline int Max(int a,int b)
  6 {
  7     return a>b?a:b;
  8 }
  9 inline int Min(int a,int b)
 10 {
 11     return a>b?b:a;
 12 }
 13 #define maxnode 600010
 14 #define sigma_size 26
 15 struct Trie
 16 {
 17     int ch[maxnode][sigma_size];
 18     int val[maxnode];
 19     int haha[maxnode];
 20     int f[maxnode];
 21     int sz;
 22     void init()
 23     {
 24         sz=1;
 25         memset(ch,0,sizeof(ch));
 26         memset(val, 0, sizeof(val));
 27         memset(f,0,sizeof(f));
 28         memset(haha,0,sizeof(haha));
 29     }
 30     int idx(char c)
 31     {
 32         return c-'a';
 33     }
 34     int insert(char *s)
 35     {
 36         int u = 0, len = strlen(s);
 37         for(int i = 0; i < len; i++)
 38         {
 39             int c = idx(s[i]);
 40             if(!ch[u][c]) ch[u][c] = sz++;
 41             u = ch[u][c];
 42         }
 43         val[u] ++;
 44         return u;
 45     }
 46     void getFail()
 47     {
 48         queue<int> q;
 49         for(int i = 0; i<sigma_size; i++)
 50             if(ch[0][i]) q.push(ch[0][i]);
 51 
 52         while(!q.empty())
 53         {
 54             int r = q.front();
 55             q.pop();
 56             for(int c = 0; c<sigma_size; c++)
 57             {
 58                 int u = ch[r][c];
 59                 if(!u)continue;
 60                 q.push(u);
 61                 int v = f[r];
 62                 while(v && ch[v][c] == 0) v = f[v]; ///沿失配边走上去 如果失配后有节点 且 其子节点c存在则结束循环
 63                 f[u] = ch[v][c];
 64             }
 65         }
 66     }
 67     void find(char *T)
 68     {
 69         int len = strlen(T), j = 0;
 70         for(int i = 0; i < len; i++)
 71         {
 72             int c = idx(T[i]);
 73             while(j && ch[j][c]==0) j = f[j];
 74             j = ch[j][c];
 75             int temp = j;
 76             while(temp)
 77             {
 78                 haha[temp]++;
 79                 temp = f[temp];
 80             }
 81         }
 82     }
 83 };
 84 Trie ac;
 85 char P[100011][10010];
 86 int ans[100010];
 87 char S1[100010];
 88 int main()
 89 {
 90     int t,m,n;
 91     scanf("%d",&t);
 92     while(t--)
 93     {
 94         ac.init();
 95         scanf("%d%d",&m,&n);
 96         for(int i = 1; i <= m; i++)
 97         {
 98             scanf("%s",P[i]);
 99         }
100         for(int i = 1; i <= n; i++)
101         {
102             scanf("%s",S1);
103             ans[i] = ac.insert(S1);
104         }
105         ac.getFail();
106         for(int i = 1; i <= m; i++)
107         {
108             memset(ac.haha,0,sizeof(ac.haha));
109             ac.find(P[i]);
110             int sum = 0;
111             for(int i=1; i <= n; i++)
112                 sum += ac.haha[ans[i]];
113             printf("%d
",sum);
114         }
115     }
116     return 0;
117 }

AC自动机--改自久野模板

模板：http://blog.csdn.net/qq574857122/article/details/12355091