AC 自動機

參考 OI-Wiki AC 自動機。

前言

2025.11.02 我之前學習 AC 自動機的時候沒有深刻理解，雖然去年市賽上現場寫出了 AC 自動機，算是大概理解了吧，但是仍然沒有寫筆記。今年 CSP 前也完全沒有復習。所以現在補上！

2025.11.03 總結了一些 AC 自動機可以做的匹配類型，但是有些還沒有寫代碼，如果有錯歡迎指出！

自動機

參考 OI-Wiki 有限狀態自動機。

支持的功能

AC 自動機可以對多個 \(s\) 建自動機，然后查詢哪些 \(s\) 是 \(t\) 的字串。

但是建好之后似乎不支持再插入新串。

建樹流程概括

1. 建出 trie 樹。

   把所有 \(s\) 插入 trie。字符串從前往后插入。

2. 構建適配指針 \(fail\)。

   \(fail_u\) 指向 \(v\)，狀態 \(v\) 是 \(u\) 的后綴，且長度最長。

struct node {
	int fail;
	// int tg;
	int son[26];
}tr[N];
int cnt;
void insert(char *s,int n) { // 在字典樹中插入串串 s
	int u = 0;
	rep(i,0,n-1) {
		int c = s[i]-'a';
		if(!tr[u].son[c]) tr[u].son[c] = ++cnt;
		u = tr[u].son[c];
	}
	// 更新 tr[u]
}
void build() { // 建 fail 樹
	// 若 rt 非 0，則需要把 tr[rt] 的所有空兒子，和 tr[rt].fail 設成 rt
	queue<int> que;
	rep(i,0,25) if(tr[0].son[i]) que.push(tr[0].son[i]); // tr[tr[0].son[i]].fail = rt
	while(que.size()) {
		int u = que.front();
		que.pop();
		rep(i,0,25) {
			if(tr[u].son[i]) {
				tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
				que.push(tr[u].son[i]);
			} else tr[u].son[i] = tr[tr[u].fail].son[i];
		}
	}
}

怎么構建失配指針？

按照 bfs 的順序求 \(fail_u\)。

現在 \(dep_x < dep_u\) 的 \(fail_x\) 都已經求好。要求 \(fail_u\)。\(fa_u\) 經過邊 \(c\) 到達 \(u\)。

• 若 \(fail_{fa_{u}}\) 經過 \(c\) 可以到達狀態 \(v\)，則 \(fail_u = v\)。
• 否則，遞歸查 \(fail_{fail_{fa_u}}\)。
• 以此類推。

特判 \(fail\) 指向根節點的時候。

欸，它的時間復雜度是多少？

跳 \(fail\) 的次數是 \(O(L)\) 的，\(L\) 是所有字符串的長度之和。不過找出邊的時候可能需要和字符集大小有關的復雜度。

具體怎么證明？

可以用勢能分析一下吧，勢能定義為在隊列里的 \(u\)（因為只有這些 \(u\) 才會需要跳 \(fail\)），\(\sum dep_{fail_u}\)。

跳 \(fail\) 的時候會消耗勢能。求出 \(fail_u\) 之后，\(u\) 的兒子會繼承 \(u\) 的勢能。假如 \(u\) 有 \(k\) 個兒子，那么節點個數就會相對 \(L\) 減少 \((k-1)dep_u\)。

所以總共消耗掉的勢能是 \(O(L)\) 的。

因為每個點只有一個 \(fail\) 指針，且指向 \(dep\) 嚴格小于它的點，所以所有 \(fail\) 指針形成一棵 \(fail\) 樹。

代碼見上面。

多模式匹配

對于字典 \(\{s_i\}\)，找有多少 \(s\) 是 \(t\) 的子串。

順序枚舉 \(t\) 的每個字符，當前在狀態 \(u\)，要經過字母 \(c\) 去到下一個狀態。

• 遍歷 \(u\) 在 \(fail\) 樹上到根的 \(fail\) 鏈，找到所有后綴狀態，加進答案。
• 如果原 trie 上 \(u\) 經過 \(c\) 可以到達 \(v\)，就直接走了。
• 否則看看 \(fail_u\) 能否經過 \(c\) 到達 \(v\)。
• 否則跳下一個適配指針。

復雜度最壞是 \(O(L^2)\) 的。

需要優化。

求哪些 \(s_i\) 在 \(t\) 中出現了

這個不用優化，直接暴力跳 fail 指針，不要跳已經跳過的節點即可。

P3808 AC 自動機（簡單版），code。

求每個 \(s_i\) 在 \(t\) 中出現多少次

在 AC 自動機里面跑 \(t\) 的時候，記錄每個狀態遇到的次數 \(tag\)。

1. 最后對 \(fail\) 樹拓撲排序（內向樹）。然后按照拓撲序記錄答案。
2. 也可以 dfs，按照 dfs 序逆序更新答案，或者遞歸回溯的時候更新答案。

只是不同的寫法而已。

P5357 【模板】AC 自動機，code。

對每個 \(t_i\)，求所有 \(s\) 在 \(t_i\) 中出現次數之和

每個狀態 \(u\) 的權值 \(w_u\) 是以 \(u\) 為終點的 \(s\) 的個數。預處理出 \(u\) 在 \(fail\) 樹上到根的和 \(sw_u\)。

然后跑 \(t\) 的時候，每個狀態加上它的 \(sw_u\)。

類似題目：P14363 [CSP-S 2025] 諧音替換 / replace，code。

對每個 \(t_i\)，求有多少 \(s\) 是它的字串

類似題目：P2336 [SCOI2012] 喵星球上的點名

https://www.luogu.com.cn/discuss/1190105

1. 簡單的哈希做法，復雜度根號。按照字符串長度分類，一共只有根號種不同的長度。然后分類哈希。https://www.luogu.com.cn/article/zevrys8n
2. 單老哥做法。跑 \(t\) 的時候每個狀態 \(u\) 需要記錄 \(u\) 在 fail 樹上到根的鏈中，沒有被算過的點。可以使用重鏈剖分維護每個重鏈的哪個前綴以及使用過；或者建所有 \(u\) 的虛樹，然后在虛樹上面統計，怎么統計都行吧。

對每個 \(s_i\)，求它在幾個 \(t_i\) 中出現了

類似題目：P5840 [COCI 2014/2015 #5] Divljak

跑 \(t\) 的時候建出 \(u\) 的虛樹。把 \(u\) 按照 dfs 序排序，然后在虛樹上面打差分標記。最后統一前綴和標記。

上面的例題，每個 \(t\) 只能對 \(k\) 個點貢獻，\(\sum k = q\)。所以需要每個虛樹在線 \(O(len+k)\) 更新貢獻。可以在虛樹上差分，在 dfs 序上用樹狀數組維護子樹和，和單點查詢。于是這個板子也可以在線做。

對每個 \(s_i\)，求它在所有 \(t_i\) 出現的次數之和

跑 \(t\) 的時候維護樹上差分標記。最后統一前綴和求出答案。

AC 自動機上 DP

這個的主要難點在 DP 了。