题目大意：
求一些字符串在一段文章中出现的次数。
思路：
AC自动机的经典应用，建完自动机直接将队列里的元素调Fail指针记录即可。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 #define M 1000009 6 #define FC x==0?0:child[fail[x]][i] 7 char s[M]; 8 int head,tail,cnt,q[M],sum[M],id[M],child[M][26],fail[M]; 9 10 void ins(int &x) 11 { 12 for (int i=0,j;i<strlen(s);i++,x=child[x][j],sum[x]++) 13 if (!child[x][j=s[i]-'a']) child[x][j]=++cnt; 14 } 15 16 void build() 17 { 18 for (head=0,tail=1;head<tail;) 19 { 20 int x=q[++head],i; 21 for (i=0;i<26;i++) 22 if (child[x][i]) q[++tail]=child[x][i],fail[child[x][i]]=FC; 23 else child[x][i]=FC; 24 } 25 } 26 27 int main() 28 { 29 int n,i; 30 scanf("%d",&n); 31 for (i=1;i<=n;i++) scanf("%s",s),ins(id[i]); 32 for (build(),i=tail;i;i--) sum[fail[q[i]]]+=sum[q[i]]; 33 for (i=1;i<=n;i++) printf("%d\n",sum[id[i]]); 34 }
转载于:https://www.cnblogs.com/HHshy/p/5754332.html
