解析

我對力量一無所知

通過這題，可以看出我對AC自動機還是完全沒有理解
qwq
首先容易想到：
建一課trie樹，然后建樹時記錄每個串s的終點，這個點后面每被經過一次，就相當于出現一次該單詞s
但是，這種“出現”：只是當s恰好是后面的前綴時，才會被計算
所以我們想到（其實到這我就沒想到 ）
任何一個以s為后綴的結點被遍歷到時，s都會出現一次
同時我們發現，這樣統計可以做到不重不漏
所以我們就可以寫出一個不倫不類的方程：

ans[s]=∑ans [s1] (s是s1的后綴)

然后利用AC自動機的機制，類似前綴和一樣的滾起來，就可以解決本題
另外值得注意的一點是，AC自動機bfs之后用完的那個隊列中恰好是按bfs排列的（廢話 ），轉移時我們可以直接利用

代碼

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+100; int tr[N][27],tot=1; int n; char s[N]; int cnt=0; int k,id[N]; int num[N]; void build(){int l=strlen(s+1),pl=1;for(int i=1;i<=l;i++){int a=s[i]-'a'+1;if(!tr[pl][a]) tr[pl][a]=++tot;pl=tr[pl][a];num[pl]++;}id[k]=pl;//num[pl]++; } int q[N],st,ed,nxt[N]; void bfs(){st=ed=q[1]=1;for(int i=1;i<=26;i++) tr[0][i]=1;nxt[1]=0;while(st<=ed){int now=q[st++];for(int i=1;i<=26;i++){if(!tr[now][i]) tr[now][i]=tr[nxt[now]][i];else{q[++ed]=tr[now][i];nxt[tr[now][i]]=tr[nxt[now]][i];}}}for(int i=ed;i>=1;i--){num[nxt[q[i]]]+=num[q[i]];}return; }int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);k=i;build();}bfs();for(int i=1;i<=n;i++){printf("%d\n",num[id[i]]);}return 0; }/* 3 a aa aaa */

總結

以上是生活随笔為你收集整理的YBTOJ：单词频率（AC自动机）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。