對于已經學了3,4遍kmp的我，竟然感覺AC自動機不太難。

?

　　kmp是解決單模式串匹配的問題，就是只能判斷一個字符串是否為另一個字符串的子串。AC自動機是解決多模式串匹配的問題，能判斷多個字符串是否同是為一個字符串的子串。

　　先從最暴力的想法入手：首先肯定要把所有模式串建成一棵trie樹，然后枚舉查詢字符串的起始點 i，看從 i 開始的子串是否能出現模式串。這就像kmp的暴力算法：尋找最大的 j，使模式串b[1 ~ j] = b[i - j + 1 ~ j]。然后我們減少無用的尋找，盡量繼承上一次尋找的答案來降低復雜度，就是線性的kmp。

　　AC自動機就是在trie樹上進行匹配，所以可以理解為trie樹上的kmp。當我們匹配到某一個節點u時，它代表的是模式串中的一些串的前綴b[1 ~ j]，同也要滿足是查詢字符串的一部分a[i - j + 1 ~ i]。這個 j 也可以理解為trie樹上這個節點的深度。當失配的時候，我們要找次長的前綴b[1 ~ k]（也就是深度比 j 小的點），看他能否等于查詢串的a[i - k + 1 ~ i]，這個k不僅僅是還是一個模式串b的前綴，可能也在trie樹上的其他鏈上的，但一定是最大的k，滿足b[1 ~ k] = a[i - k + 1 ~ i]。

　　接著考慮具體怎么實現：kmp的狀態轉移是從i - 1轉移過來的，所以在trie樹上就是從其父親節點轉移，因此要保證對于u，深度比u小的點的失配指針都已經構造好了。所以可以從根節點開始bfs，對于當前隊首的節點u，構造u的所有兒子節點的失配指針：如果失配，就沿著父親的失配指針往上跳，直到找到一個節點的下一個狀態和當前節點一樣。

　　但正是因為構造每一個節點的fail時要挑好多次，所以可能會超時，解決的辦法就是構造虛擬節點：對于u的一個不存在的兒子ch[u][i]，讓ch[u][i] = ch[fail[u]][i]，也就是直接指向一個最長的前綴b[1 ~ j]，使節點u的下一個字符如果是 i 的話，保證b[1 ~ j]= b[i - j + 1 ~ i]。這樣如果v = ch[now][i]存在的話，fail[v] = ch[fail[now]][i]。

　　有人會問，如果ch[fail[u]][i]也不存在呢？這是不可能的，因為如果ch[fail[u]][i]不存在的話，那么他存的值是ch[ch[fail[u][i]][i]。

　　查詢其實因題而異，比如這個板子。只用統計出現次數，那么跑ac自動機的時候如果這個模板串已經找出來了，就改了他的val，避免重復統計。

　　具體實現就是像kmp一樣，沿著失配邊往后跳，沿路統計所有節點的val，并改成-1，證明已經走過了。那么終止條件要么是跳到頭了，要么是val[j] = -1。因為如果val[j] = -1，那么fail[j], fail[fail[j]]一定都是-1.

放一個這道題的代碼

1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e6 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), las = ' '; 25 while(!isdigit(ch)) las = ch, ch = getchar(); 26 while(isdigit(ch)) ans = ans * 10 + ch - '0', ch = getchar(); 27 if(las == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) putchar('-'), x = -x; 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n; 38 char s[maxn]; 39 40 int ch[maxn][30], cnt = 0, val[maxn], f[maxn]; 41 42 int getnum(char c) 43 { 44 return c - 'a'; 45 } 46 void insert(char *s) 47 { 48 int m = strlen(s); 49 int now = 0; 50 for(int i = 0; i < m; ++i) 51 { 52 int c = getnum(s[i]); 53 if(!ch[now][c]) ch[now][c] = ++cnt; 54 now = ch[now][c]; 55 } 56 val[now]++; 57 } 58 void build() 59 { 60 queue<int> q; 61 for(int i = 0; i < 26; ++i) 62 if(ch[0][i]) q.push(ch[0][i]); 63 while(!q.empty()) 64 { 65 int now = q.front(); q.pop(); 66 for(int i = 0; i < 26; ++i) 67 { 68 if(ch[now][i]) f[ch[now][i]] = ch[f[now]][i], q.push(ch[now][i]); 69 else ch[now][i] = ch[f[now]][i]; 70 } 71 } 72 } 73 int query(char *s) 74 { 75 int len = strlen(s), now = 0, ans = 0; 76 for(int i = 0; i < len; ++i) 77 { 78 int c = getnum(s[i]); 79 now = ch[now][c]; 80 for(int j = now; j && val[j] != -1; j = f[j]) ans += val[j], val[j] = -1; 81 } 82 return ans; 83 } 84 85 int main() 86 { 87 n = read(); 88 for(int i = 1; i <= n; ++i) 89 { 90 scanf("%s", s); 91 insert(s); 92 } 93 build(); 94 scanf("%s", s); 95 write(query(s)); enter; 96 return 0; 97 } View Code

?

轉載于:https://www.cnblogs.com/mrclr/p/9768085.html

總結

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

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