【题意】
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
【分析】
个人觉得是用了反fail树的思想，Ans[i]=t[i].cnt+∑Ans[反fail]...不过因为有些节点的反fail会有很多个，存起来不方便。但是AC自动机的fail却只有一个，而且我们在建立AC自动机的时候是用类似宽搜的方法建的，所以保存在队列里的节点肯定是由深到浅。然后我们就可以从后往前for一遍，把i的cnt加入到i的fail的cnt里，最后每个单词最末节点的cnt就是答案。
代码如下：
1 #include2 #include 3 #include 4 5 const int Maxn=(int)1e4; 6 const int Maxl=200; 7 8 struct node 9 {10 int son[27],fail,cnt,ans;11 }t[16035707];12 13 int n,m,cnt=0;14 int q[Maxn*Maxl+10],bj[Maxn];15 char s[Maxl];16 17 void floy()18 {19 int i;20 for(i=1;i<=Maxn;i++) t[i].fail=0,t[i].ans=0;21 }22 23 void read() 24 {25 memset(bj,0,sizeof(bj));26 int i,j,x,ind;27 scanf("%d",&n);28 getchar();29 for(i=1;i<=n;i++)30 {31 scanf("%s",s+1);32 m=strlen(s+1);33 x=0;34 for(j=1;j<=m;j++)35 {36 ind=s[j]-'a'+1;37 if(!t[x].son[ind]) t[x].son[ind]=++cnt;38 x=t[x].son[ind];39 t[x].cnt++;40 if(j==m) bj[i]=cnt;41 }42 }43 }44 45 void Build_AC()46 {47 int i,x,y,j;48 q[0]=0;49 q[++q[0]]=0;50 //for(i=1;i<=26;i++) if(t[0].son[i]) q[++q[0]]=t[0].son[i]; 51 for(i=1;i<=q[0];i++)52 {53 x=q[i];54 y=t[x].fail;55 for(j=1;j<=26;j++)56 if(t[x].son[j]) 57 { 58 //t[t[x].son[j]].fail=t[y].son[j];59 t[t[x].son[j]].fail=x?t[y].son[j]:x; 60 q[++q[0]]=t[x].son[j]; 61 }62 else t[x].son[j]=t[y].son[j];63 }64 for(i=q[0];i>=1;i--)65 {66 t[t[q[i]].fail].cnt+=t[q[i]].cnt;67 }68 }69 70 int main()71 {72 read();73 Build_AC();74 for(int i=1;i<=n;i++) printf("%d\n",t[bj[i]].cnt);75 }
2016-07-12 10:12:39