傳送門

初學ac自動機。
ac自動機相當于在trie上建立kmp中的ne指針（fail樹）

建樹的函數build()比較固定；利用bfs+queue的特點還可以同時求出trie的拓撲序。

匹配的時候就可以靈活操作了。。

題意

某人讀論文，一篇論文是由許多單詞組成的。

但他發現一個單詞會在論文中出現很多次，現在他想知道每個單詞分別在論文中出現多少次。

輸入格式
第一行一個整數 N，表示有多少個單詞。

接下來 N 行每行一個單詞，單詞中只包含小寫字母。

輸出格式
輸出 N 個整數，每個整數占一行，第 i 行的數字表示第 i 個單詞在文章中出現了多少次。

數據范圍
1≤N≤200,
所有單詞長度的總和不超過 106。

輸入樣例：
3
a
aa
aaa
輸出樣例：
6
3
1

分析

先建立自動機，發現只需要統計每個單詞能被多少個節點跳到就行了。

舉例： s=“abcd”; t=“abcdeabcde”
在trie樹上：
t[3]會指向s[3]（也就是自己，s[3]在trie樹上與t[3]是同一個位置，統計為cnt[s[3]]=2）
t[8]會指向s[3]（在trie樹上與t[3]是同一個位置）
所以，s[3]這個位置的cnt初值為2，又被一個節點指向了->ans=3。
解釋的很抽象，，

于是：將所有單詞建立trie圖之后，利用順便求出來的拓撲序自底向上更新每個節點的答案值就行了。

代碼

#include <bits/stdc++.h>using namespace std; //-----pre_def---- const double PI = acos(-1.0); const int INF = 0x3f3f3f3f; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<double, double> PDD; #define fir(i, a, b) for (int i = (a); i <= (b); i++) #define rif(i, a, b) for (int i = (a); i >= (b); i--) #define endl '\n' #define init_h memset(h, -1, sizeof h), idx = 0; #define lowbit(x) x &(-x)//--------------- const int N = 1e6 + 10; int n; int tr[N][26], cnt[N], ne[N], idx; char str[N]; int id[210]; int q[N]; void init() {memset(tr, 0, sizeof tr);memset(cnt, 0, sizeof cnt);memset(ne, 0, sizeof ne);idx = 0; }void insert(int x) {int root = 0;for (int i = 0; str[i]; i++){int now = str[i] - 'a';if (!tr[root][now])tr[root][now] = ++idx;root = tr[root][now];cnt[root]++;}id[x] = root; }void ne_build() {int hh = 0, tt = -1;fir(i, 0, 25) if (tr[0][i]) q[++tt] = tr[0][i];while (hh <= tt){auto t = q[hh++];fir(i, 0, 25){int now = tr[t][i];if (now){ne[now] = tr[ne[t]][i];q[++tt] = now;}else{tr[t][i] = tr[ne[t]][i];}}} }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);int StartTime = clock(); #endifscanf("%d", &n);fir(i, 1, n){scanf("%s", str);insert(i);}ne_build(); //還可以順便做topsortrif(i, idx - 1, 0)//queue中一共存過idx個點，編號從0開始 所以是0~idx-1。{cnt[ne[q[i]]] += cnt[q[i]];}fir(i, 1, n) printf("%d\n", cnt[id[i]]); #ifndef ONLINE_JUDGEprintf("Run_Time = %d ms\n", clock() - StartTime); #endifreturn 0; }

總結

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

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