傳送門

Description

某人讀論文，一篇論文是由許多單詞組成。但他發(fā)現(xiàn)一個單詞會在論文中出現(xiàn)很多次，現(xiàn)在想知道每個單詞分別在論文中出現(xiàn)多少次。

Input

第一個一個整數(shù)N,表示有多少個單詞，接下來N行每行一個單詞。每個單詞由小寫字母組成，N<=200,單詞長度不超過10^6

Output

輸出N個整數(shù)，第i行的數(shù)字表示第i個單詞在文章中出現(xiàn)了多少次。

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

哎，這不是多字符串的問題嗎？我們首先就想到了AC自動機！
fail指針的意義是什么呢？就是一個后綴鏈接，而后綴是覆蓋了所有的子串的，所以我們可以用一次樹DP，就統(tǒng)計出了每一個單詞出現(xiàn)的次數(shù)。

/**************************************************************Problem: 3172User: geng4512Language: C++Result: AcceptedTime:256 msMemory:237132 kb ****************************************************************/#include<cstdio> #define MAXN 2000000 #define MAXC 26 int a[MAXN][MAXC], pre[MAXN], sz = 1, q[MAXN], cnt[MAXN], ed[MAXN], n; char s[MAXN]; inline int Insert(char *s) {int c, p = 1;for(int i = 0; s[i]; ++ i) {c = s[i] - 'a';if(!a[p][c]) a[p][c] = ++ sz;p = a[p][c]; ++ cnt[p];}return p; } void Build() {int l = 1, r = 0;for(int i = 0; i < MAXC; ++ i)if(!a[1][i]) a[1][i] = 1;else {pre[a[1][i]] = 1;q[++ r] = a[1][i];}while(l <= r) {int u = q[l ++];for(int i = 0; i < MAXC; ++ i)if(!a[u][i]) a[u][i] = a[pre[u]][i];else {pre[a[u][i]] = a[pre[u]][i];q[++ r] = a[u][i];}}for(int i = r; i; -- i) cnt[pre[q[i]]] += cnt[q[i]]; } int main() {scanf("%d", &n);for(int i = 1; i <= n; ++ i) {scanf("%s", s);ed[i] = Insert(s);}Build();for(int i = 1; i <= n; ++ i) printf("%d\n", cnt[ed[i]]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/geng4512/p/5296869.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3172 TJOI2013 单词的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。