引入

AC自动机是什么呢 首先要知道KMP，KMP是单字符串匹配 接下来要知道字典树，是用来存一堆字符串 AC自动机就是它们合起来：多字符串匹配

用一个网上很多人举的例子 在一篇文章中找出某些字符串出现的次数就是AC自动机的作用

建trie

fo(i,1,m) { scanf("%s",t+1); scanf("\n"); int k=1; fo(j,1,strlen(t+1)) { int l=t[j]-96; if (c[k][l]==0) c[k][l]=++tot; deep[c[k][l]]=deep[k]+1;k=c[k][l]; } c[k][0]=1;//在每个串的结尾标记一下 }

fail

KMP有个next数组 到了AC自动机，有个一样作用的fail数组 建fail的思想自己YY或找国家队论文，网上很多资料不靠谱 建fail程序

void buildfail() { int j=1,h=0;d[j]=1; for(;h<j;) { int k=d[++h],p=0; fo(i,1,26) if(c[k][i]!=0) { int p=c[k][i]; if(p) { int z=fail[k]; while(z!=0&&c[z][i]==0) z=fail[z]; fail[p]=c[z][i]; d[++j]=p; } fail[p]=(fail[p]==0)?1:fail[p]; up[p]=p; } } }

用队列，c数组是trie，第二维就是代表26个字母

查询

查询也就差不多了，对于每一次都从fail链上走过即可

void query() { int k=1; fo(i,1,n) { int j=s[i]-96; while(k!=1 && c[k][j]==0) k=fail[k]; k=c[k][j];k=(k==0)?1:k; while (p!=1) { if(c[p][0]==1) ans++; p=fail[p]; 如果不能重复的话就把c[p][0]标记为负数就行了 } } }

套上题目，灵活运用，加上各种优化。

模板题：贴瓷砖

Description

A镇的主街是由N个小写字母构成，镇长准备在上面贴瓷砖，瓷砖一共有M种，第i种上面有Li个小写字母，瓷砖不能旋转也不能被分割开来，瓷砖只能贴在跟它身上的字母完全一样的地方，允许瓷砖重叠，并且同一种瓷砖的数量是无穷的。 问街道有多少字母(地方)不能被瓷砖覆盖。

Input

第一行输入街道长度N(1<=N<=300,000)。 第二行输入N个英文小写字母描述街道的情况。 第三行输入M(1<=M<=5000)，表示瓷砖的种类。 接下来M行，每行描述一种瓷砖，长度为Li(1<=Li<=5000)，全部由小写字母构成。

Output

输出有多少个地方不能被瓷砖覆盖。

Sample Input

输入1： 6 abcbab 2 cb cbab 输入2： 4 abab 2 bac baba 输入3： 6 abcabc 2 abca cab

Sample Output

输出1： 2 输出2： 4 输出3： 1

Data Constraint

N(1<=N<=300,000)

这题就是AC自动机的裸题

加个小优化：用up[x]表示x沿fail链上的第一个有值的点，这样就不用循环了 求答案就线段覆盖咯~~

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define fo(i,a,b) for(int i=a;i<=b;i++) #define N 301000 #define M 5010 using namespace std; char s[N],t[M]; int n,m,fail[M*1000],deep[M*1000],c[M*800][28],ans[N][2],bz[N],up[M*1000],tot=1,d[M*1000]; void buildfail() { int j=1,h=0;d[j]=1; for(;h<j;) { int k=d[++h],p=0; fo(i,1,26) if(c[k][i]!=0) { int p=c[k][i]; if(p) { int z=fail[k]; while(z!=0&&c[z][i]==0) z=fail[z]; fail[p]=c[z][i]; d[++j]=p; } fail[p]=(fail[p]==0)?1:fail[p]; up[p]=p; if(c[up[p]][0]==0&&up[p]!=1) up[p]=up[fail[p]];//求up } } } void query() { int k=1; fo(i,1,n) { int j=s[i]-96; while(k!=1 && c[k][j]==0) k=fail[k]; k=c[k][j];k=(k==0)?1:k; ans[++ans[0][0]][0]=i;ans[ans[0][0]][1]=deep[up[k]]; //因为题目的特殊，求答案也可以特殊一点 } } int main() { freopen("ACauto.in","r",stdin); scanf("%d\n",&n); scanf("%s",s+1); scanf("%d\n",&m); fo(i,1,m) { scanf("%s",t+1); scanf("\n"); int k=1; fo(j,1,strlen(t+1)) { int l=t[j]-96; if (c[k][l]==0) c[k][l]=++tot; deep[c[k][l]]=deep[k]+1;k=c[k][l]; } c[k][0]=1; } buildfail(); query(); fo(i,1,ans[0][0]) { bz[ans[i][0]+1]--;bz[ans[i][0]-ans[i][1]+1]++; } int an=0,jy=0; fo(i,1,n) { jy+=bz[i];if(jy==0) an++; } printf("%d",an); }