传送门：://acm.hdu.edu.cn/showproblem.php?pid=2222
思路：AC自动机入门题，直接上AC自动机即可。
对于构建AC自动机，我们要做的只有三件事：
1）构建字典树
2）构建失败指针
3）构建trie图（这道题好像不做这一步也能A。。。但是这一步不做是会被卡成O(n^2)的。。。）
1）第一步还是比较好理解的
根是虚根，边代表字母，那么根到终止节点的路径就是一个字符串，这样对于前缀相同的字符串我们就可以省下存公共前缀的空间。
加入一个模式串，我们就在trie树上一步一步走，没有这个儿子就新建，否则就按原来的边走。
2）第二步有一点复杂。
学AC自动机要有KMP的基础原因就在这里。fail指针就是KMP的next数组在有多个模式串时的升级版
KMP的next数组是指同一个模式串中，既是最长前缀又是后缀的子串的长度，，这么定义是为了方便在匹配失败时跳转
而fail指针的作用也是为在匹配失败时跳转。因为是多串，一个点的fail指针指向与这一段的后缀相同的，另一个串前缀，这样就实现了在匹配失败时跳转。画个图更直观
然后就是求出fail指针了。求next数组时，我们可以由之前的next数组进行跳转得到现在的next数组，求fail指针也很类似。
我们可以一层一层地用bfs求出fail指针。
1.根节点的fail指向null，根节点的子节点的fail指向根（因为第一位就不匹配了，当然要重新开始）
2.求完fail的放到队尾
3.取出队头节点x，求它的所有儿子ch[x][i]的fail指针
如果ch[x][i]存在，那么fail[ch[x][i]]=ch[fai[x]][i]（其实应该一直跳fail直到ch[x][i]存在，这也是不构建trie图会被卡成O(n^2)的原因，把不存在的儿子补好后，就只要跳一次了）
否则ch[x][i]=ch[fail[x]][i]（其实就是第三步构建trie图，把所有不存在的儿子补好，省得每次跳很多次fail）
4.重复2和3直到队列为空
这样,AC自动机就构建好了
然后就是代码了。。。
#include<cstdio>#include<cstring>#include<algorithm>const int maxn=1000010,maxm=250010;using namespace std;int cas,n;char s[maxn];struct AC_DFA{int tot,ch[maxm][26],fai[maxm],sum[maxm],q[maxm],head,tail;void clear(){tot=0,memset(ch,0,sizeof(ch)),memset(fai,0,sizeof(fai)*2);}void insert(){int p=0;for (int i=1;s[i];p=ch[p][s[i]-'a'],i++) if (!ch[p][s[i]-'a']) ch[p][s[i]-'a']=++tot;sum[p]++;}void getfail(){head=0,q[tail=1]=0,fai[0]=-1;while (head!=tail){int x=q[++head];for (int i=0;i<26;i++)if (ch[x][i]){q[++tail]=ch[x][i];int p=x==0?0:ch[fai[x]][i];//while (p!=-1&&!ch[p][i]) p=fai[p];fai[ch[x][i]]=p;}else ch[x][i]=x==0?0:ch[fai[x]][i];}}void work(){int ans=0;for (int i=1,p=0;s[i];i++){while (p&&!ch[p][s[i]-'a']) p=fai[p];p=ch[p][s[i]-'a'];for (int t=p;t;t=fai[t]) ans+=sum[t],sum[t]=0;//printf("%d %d\n",t,sum[t]),}printf("%d\n",ans);}}T;int main(){scanf("%d",&cas);while (cas–){scanf("%d",&n);T.clear();for (int i=1;i<=n;i++)scanf("%s",s+1),T.insert();T.getfail(),scanf("%s",s+1),T.work();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
不要轻言放弃，否则对不起自己
