題面：https://www.luogu.org/problemnew/show/P3966

大意：小張最近在忙畢設,所以一直在讀論文。一篇論文是由許多單詞組成但小張發現一個單詞會在論文中出現很多次,他想知道每個單詞分別在論文中出現了多少次。

這次沒有文本串。

用了個奇妙的方法。

a[x] 表示第x個串結尾的位置。

在bfs搜索求fail的時候手寫，將所有的點都保存下來了。

num(x)則為經過這個點x的個數。

自然num(fail(x))+=num(x)。

所有經過x的串都能經過fail(x)。

最后求所有a[x]的num就是答案了。

代碼如下。

#include<bits/stdc++.h> #define sc(x) scanf("%d",&x) using namespace std; const int maxn=1e6+10; int n,cnt; struct trie{int fail,num;int ch[30];#define fa(x) ac[x].fail#define nu(x) ac[x].num }ac[maxn]; int a[maxn],h[maxn]; inline void insert(string s,int x){int len=s.length();int now=0;for(int i=0;i<len;i++){if(!ac[now].ch[s[i]-'a'])ac[now].ch[s[i]-'a']=++cnt;now=ac[now].ch[s[i]-'a'];nu(now)++;}a[x]=now; } //bfs inline void getfail(){int head=0;int tail=0;for(int i=0;i<26;i++)if(ac[0].ch[i])fa(ac[0].ch[i])=0,h[++tail]=ac[0].ch[i];while(head<tail){int now=h[++head];for(int i=0;i<26;i++){if(ac[now].ch[i]){fa(ac[now].ch[i])=ac[fa(now)].ch[i];h[++tail]=ac[now].ch[i];}elseac[now].ch[i]=ac[fa(now)].ch[i];}} } inline void ask(){for(int i=cnt;i>=0;i--) nu(fa(h[i]))+=nu(h[i]);for(int i=1;i<=n;i++) printf("%d\n",nu(a[i])); } int main() {sc(n);string s;for(int i=1;i<=n;i++){cin>>s;insert(s,i);}fa(0)=0;getfail();ask();// while(1);return 0; }

話說和網上大佬學的struct 存trie感覺挺有意思。

改不過來了。

轉載于:https://www.cnblogs.com/ChrisKKK/p/11144072.html

總結

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

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