题意：
给n个模式串和1个主串，求他们在主串中出现的次数，子串不重复计数。
分析：
AC自动机模板题，在处理子串的时候要特殊处理，原来AC自动机是没必要写一个update_fail函数的，，这已经是比较简洁的模板了。
代码：
//poj 4052//sep9#include <iostream>#include <queue>using namespace std;struct Node{int s[32],fail,fa;bool word,vis;}a[200000];bool tag[200000];char s[5120000];char ss[5120000];int index;queue<int> Q;void decompress(){int p=0,q=0;while(s[p]!='\0'){if(s[p]>='A'&&s[p]<='Z')ss[q++]=s[p++];else{++p;int sum=0;while(s[p]>='0'&&s[p]<='9'){sum=sum*10+(s[p]-'0');++p;}char c=s[p++];while(sum–)ss[q++]=c;++p;}}ss[q]='\0';}void insert(){int h=0,i=0,tmp;while(ss[i]!='\0'){int k=ss[i]-'A';if(!a[h].s[k])a[h].s[k]=++index;tmp=h;h=a[h].s[k];a[h].fa=tmp;++i;}a[h].word=true;}void dfs_clear(int x){if(tag[x]==true) return;a[x].vis=false;tag[x]=true;dfs_clear(a[x].fail);dfs_clear(a[x].fa);}void build_AC_Automation(){while(!Q.empty()) Q.pop();Q.push(0);while(!Q.empty()){int h=Q.front();Q.pop();for(int i=0;i<26;++i)if(a[h].s[i]){Q.push(a[h].s[i]);if(h) a[a[h].s[i]].fail=a[a[h].fail].s[i];}elsea[h].s[i]=a[a[h].fail].s[i];}}int main(){int cases;scanf("%d",&cases);while(cases–){memset(a,0,sizeof(a));index=0;int n;scanf("%d",&n);while(n–){scanf("%s",s);decompress();insert();}build_AC_Automation();scanf("%s",s);decompress();int ans=0,h=0;for(int i=0;ss[i]!='\0';++i){h=a[h].s[ss[i]-'A'];if(a[h].word==true)a[h].vis=true;}memset(tag,0,sizeof(tag));for(int i=0;i<=index;++i)if(tag[i]==false&&a[i].vis==true){dfs_clear(a[i].fa);dfs_clear(a[i].fail);}for(int i=0;i<=index;++i)if(a[i].vis==true)++ans;printf("%d\n",ans);}return 0;}
生气是拿别人做错的事来惩罚自己
