BZOJ3172: [Tjoi2013]單詞

【傳送門：BZOJ3172】

---

簡要題意：

　　給出n個單詞，你可以理解為將這些單詞變成一個個段落，然后求出每個單詞在所有段落中出現的次數

---

題解（一）：

　　剛開始不是很懂題目，結果發現將所有單詞看成一篇文章，每個單詞看成一個段落就懂了

　　由于某種unbelievable的原因，我剛好做了AC自動機的專題訓練，看到這道題就秒想AC自動機

　　將每個單詞放進AC自動機里，每個點的s表示有多少個單詞經過，然后在構建失敗指針的時候，通過隊列來更新s值，怎么更新呢，假設有一個i點，它的失敗指針指向j，設sj為從根到j點所構成的字符串，si為從根到i點所構成的字符串，那么我們可以知道sj為si的后綴，也說明了si中有sj的出現，那么就將j點的s值加上i點的s值，達到更新且不重復的目的來求出答案

---

?

參考代碼（一）：

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
struct node
{int s,c[27],fail;node(){s=fail=0;memset(c,-1,sizeof(c));}
}t[1100000];
int tot,ans,n;
char a[1100000];
int ed[210];
void bt(int k,int root)
{int x=root,len=strlen(a+1);for(int i=1;i<=len;i++){int y=a[i]-'a'+1;if(t[x].c[y]==-1){t[x].c[y]=++tot;}x=t[x].c[y];t[x].s++;}ed[k]=x;
}
int list[1100000];
void bfs()
{int x;int head=1,tail=1;list[1]=0;while(head<=tail){x=list[head];for(int i=1;i<=26;i++){int son=t[x].c[i];if(son==-1)continue;if(x==0) t[son].fail=0;else{int j=t[x].fail;while(j!=0&&t[j].c[i]==-1) j=t[j].fail;t[son].fail=max(t[j].c[i],0);int x=t[son].fail,y=son;}list[++tail]=son;}head++;}for(int i=tail;i>=1;i--) t[t[list[i]].fail].s+=t[list[i]].s;
}
int main()
{ans=tot=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",a+1);bt(i,0);}bfs();for(int i=1;i<=n;i++){printf("%d\n",t[ed[i]].s);}return 0;
}

?

---

?

題解（二）：

　　 ?A了這道題之后才發現早在之前就A了（心酸）

　　那我們就來搞一下第二種想法

　　很容易就想到AC自動機，但是單單是AC自動機還不行

　　這時就要用AC自動機的延伸——fail樹來做（時常膜一膜算法，有益身體健康）

　　fail樹這個玩意就是將AC自動機中fail指針當成是一條邊，然后建成一棵樹

　　由于trie樹上的每個點相當于一個字符串，所以這棵fail樹父親節點是兒子節點所構成字符串的最長后綴

　　這樣子對于這道題而言，fail樹簡直就是神一般的存在QAQ

　　首先將每個字符串放進trie樹里面，并且每經過一個trie樹里的點，就用s數組記錄這個字符串出現的個數，每經過一次就加一，然后構造AC自動機，然后在構造AC自動機的過程中，對每個點的fail指針進行建邊，然后用dfs從根往下遍歷，把s數組從下往上累加

　　然后在輸入每個字符串的時候，記錄每個字符串的最后一個字符在trie樹上的編號，然后一個一個輸出s[end[i]]（end[i]表示第i個字符串最后一個字母在trie樹上的編號）

---

參考代碼（二）：

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
struct node
{int c[27],fail;node(){fail=0;memset(c,-1,sizeof(c));}
}t[1100000];
int tot,n;
char st[1100000];
int s[1100000];
int end[1100000];
void bt(int root,int z)
{int x=root,len=strlen(st+1);for(int i=1;i<=len;i++){int y=st[i]-'a'+1;if(t[x].c[y]==-1){t[x].c[y]=++tot;}x=t[x].c[y];s[x]++;}end[z]=x;
}
struct edge
{int x,y,next;
}a[1100000];int len,last[1100000];
void ins(int x,int y)
{len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;
}
queue<int> q;
void bfs()
{int x;q.push(0);while(q.empty()==0){x=q.front();for(int i=1;i<=26;i++){int son=t[x].c[i];if(son==-1)continue;if(x==0) t[son].fail=0;else{int j=t[x].fail;while(j!=0&&t[j].c[i]==-1) j=t[j].fail;t[son].fail=max(t[j].c[i],0);}ins(t[son].fail,son);q.push(son);}q.pop();}
}
void dfs(int x)
{for(int k=last[x];k;k=a[k].next){int y=a[k].y;dfs(y);s[x]+=s[y];}
}
int main()
{tot=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",st+1);bt(0,i);}len=0;memset(last,0,sizeof(last));bfs();dfs(0);for(int i=1;i<=n;i++) printf("%d\n",s[end[i]]);return 0;
}

?

?