AC自动机模板
AC 自动机 (Aho-Corasick Automaton) 并不是能让程序自动 AC 的机器。。而是一种有限确定自动机 (Deterministic Finite Automata, DFA)。
AC 自动机可以理解为 Trie + KMP,即用多个模式串建立 Trie,然后用 BFS 求出失配指针 fail。可以解决多个模式串在一个文本串中是否出现的问题。
如下图,黑边为 Trie 树边,红边和蓝边为 fail 指针。
以下是洛谷 3808 【模板】AC自动机(简单版)的代码,题意即为上述的带下划线的问题。
Code: O(L), 其中L为所有串长度和 [56597K, 260MS]
// Aho-Corasick Automaton (2018.2.26) // 洛谷 3808 【模板】AC自动机(简单版) // 给定 n 个模式串和 1 个文本串,求有多少个模式串在文本串里出现过 #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int MAXLEN = 1000002; int n; char p[MAXLEN]; struct Aho_Corasick_Automaton{ int trie[MAXLEN][26], cnt[MAXLEN], fail[MAXLEN], topp; queue<int> q; inline void insert(char *str){ int len = strlen(str), cur = 0; for(register int i = 0; i < len; i++){ int v = str[i] - 'a'; if(!trie[cur][v]) trie[cur][v] = ++topp; cur = trie[cur][v]; } cnt[cur]++; } // 建立 Trie inline void build_fail(){ for(register int i = 0; i < 26; i++) if(trie[0][i]) fail[trie[0][i]] = 0, q.push(trie[0][i]); // 根的子树 fail 指向根 while(!q.empty()){ int u = q.front(); q.pop(); for(register int i = 0; i < 26; i++) if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i], q.push(trie[u][i]); // 子节点 fail 指向当前节点 fail 的同位子节点 else trie[u][i] = trie[fail[u]][i]; // 合并优化 } } inline int query(char *str){ int len = strlen(str), cur = 0, res = 0; for(register int i = 0; i < len; i++){ cur = trie[cur][str[i] - 'a']; for(register int j = cur; j && ~cnt[j]; j = fail[j]) res += cnt[j], cnt[j] = -1; // 仅统计一次 } return res; } } AC; int main(){ scanf("%d", &n); for(register int i = 1; i <= n; i++) scanf("%s", p), AC.insert(p); AC.build_fail(); scanf("%s", p), printf("%d\n", AC.query(p)); return 0; }
666
%%%%%%%%%%%%
NOI___GOD->lsh
%%%%%%%%%%%%

willem
%%%zby