洛谷P3966 [TJOI2013]單詞 題解

題目鏈接：P3966 [TJOI2013]單詞

題意：

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

$1\le n\le 200$，單詞總長度不超過 $10^6$。

瞎搞做法能跑到最優解前3頁也是有趣

這個文章看樣例應該是單詞間有空格的

于是我們就把所有單詞全部加上去，用 $\#$ 分隔

然后就變成 P5357 AC自動機二次加強版 了

具體的就是把暴力跳fail數組改成topo排序更新

時間復雜度 $O(26\times \sum s_i)$

代碼：

#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> #include <queue> using namespace std; // #define int long long // #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(205) #define L (int)(1e6+215)int n,f[N],fail[L],val[L],in[L],ans[N]; string s,t; struct Trie {queue<int> q;int tot,trie[L][26],ed[L];void insert(string s,int id){int u=0;for(int i=0; i<s.size(); i++){int c=s[i]-'a';if(!trie[u][c])trie[u][c]=++tot;u=trie[u][c];}if(!ed[u])ed[u]=id;f[id]=ed[u];}void build(){for(int i=0; i<26; i++)if(trie[0][i])q.push(trie[0][i]);while(!q.empty()){int u=q.front();q.pop();for(int i=0; i<26; i++){if(trie[u][i]){fail[trie[u][i]]=trie[fail[u]][i];++in[trie[fail[u]][i]];q.push(trie[u][i]);}else trie[u][i]=trie[fail[u]][i];}}}void AC(){int u=0;for(int i=0; i<t.size(); i++){if(t[i]=='#')u=0;else u=trie[u][t[i]-'a'];++val[u];}for(int i=1; i<=tot; i++)if(!in[i])q.push(i);while(!q.empty()){u=q.front(); q.pop();if(ed[u])ans[ed[u]]=val[u];val[fail[u]]+=val[u];if(!--in[fail[u]])q.push(fail[u]);}} }tr; signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// freopen("check.in","r",stdin);// freopen("check.out","w",stdout);cin >> n;for(int i=1; i<=n; i++){cin >> s; t+=s+"#";tr.insert(s,i);}tr.build(); tr.AC();for(int i=1; i<=n; i++)cout << ans[f[i]] << '\n';return 0; }

轉載請說明出處

總結

以上是生活随笔為你收集整理的洛谷P3966 [TJOI2013]单词 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

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