[AC自動機][學習筆記]

用途

AC自動機適用於一類用多個子串在模板串中匹配的字元串問題。

也就是說先給出一個模板串，然後給出一些子串。要求有多少個子串在這個模板串中出現過。

KMP與trie樹

其實AC自動機就是KMP與trie的結合版。或者說是在trie上進行的kmp演算法。所以學會kmp和trie是學習AC自動機的基礎。

對於上面那類問題。可以對於每個子串都用kmp演算法在母串中匹配一次。但是複雜度就成了\(n^2\)

AC自動機

而對於這類問題，AC自動機的實現是先把所有的子串都掛到trie樹上，然後在用母串去trie上匹配。

首先往trie上掛子串和普通的trie一樣。就像這樣

void add() {
   int len = strlen(s + 1);
   int now = 0;
   for(int i = 1;i <= len;++i) {
      if(!trie[now][s[i] - 'a']) trie[now][s[i] - 'a'] = ++tot;
      now = trie[now][s[i] - 'a'];
   }
   val[now]++;
}

然後就要建立失配指針。也就是建立起一張trie圖，與trie樹的區別是這是一張圖。(廢話)。和kmp類似。如果當前節點下麵有x這個字元，那麼x的失配指針就指向當前節點失配指針的x孩子。否則，當前節點的兒子就是當前節點失配指針的x孩子。

代碼就像這樣

void build() {
   for(int i = 0;i < 26;++i) if(trie[0][i]) fail[trie[0][i]] = 0,q.push(trie[0][i]);
   while(!q.empty()) {
      int u = q.front();q.pop();
      for(int i = 0;i < 26;++i) {
         if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i],q.push(trie[u][i]);
         else trie[u][i] = trie[fail[u]][i];
      }
   }
}

查詢，那麼如何查詢呢。其實也很簡單，像在trie樹上查詢一樣在這個trie圖上查詢母串。每查詢到一個節點，就不斷的沿著他的fail指針跳，然後加上跳到的節點的標記(用來標記當前節點是多少個子串的結尾的標記)。並且標記為訪問過了，防止以後重覆訪問。

代碼就像這樣

int query() {
   int now = 0;
   int ans = 0;
   int len = strlen(S + 1);
   for(int i = 1;i <= len;++i) {
      now = trie[now][S[i] - 'a'];
      for(int j = now;j && val[j] != -1;j = fail[j]) ans += val[j],val[j] = -1; 
   }
   return ans;
}

其實AC自動機的用途非常廣泛，並不是只能處理這一類問題。在各種題目中可以見到他的很多應用。