參考資料：AC自動機GIF動圖（來自油管）

以下文章節(jié)選自：王爭老師 AC自動機：如何用多模式串匹配實現(xiàn)敏感詞過濾功能浊仆？

AC 自動機實際上就是在 Trie 樹之上腮猖，加了類似 KMP 的 next 數(shù)組凡伊，只不過此處的 next 數(shù)組是構(gòu)建在樹上罷了糠馆。如果代碼表示橘茉，就是下面這個樣子：

public class AcNode {
  public char data; 
  public AcNode[] children = new AcNode[26]; // 字符集只包含 a~z 這 26 個字符
  public boolean isEndingChar = false; // 結(jié)尾字符為 true
  public int length = -1; // 當 isEndingChar=true 時，記錄模式串長度
  public AcNode fail; // 失敗指針
  public AcNode(char data) {
    this.data = data;
  }
}

所以朱庆，AC 自動機的構(gòu)建盛泡，包含兩個操作：

• 將多個模式串構(gòu)建成 Trie 樹；
• 在 Trie 樹上構(gòu)建失敗指針（相當于 KMP 中的失效函數(shù) next 數(shù)組）娱颊。

關(guān)于如何構(gòu)建 Trie 樹，請參考Trie樹的部分凯砍。所以箱硕，這里我們就重點看下，構(gòu)建好 Trie 樹之后悟衩，如何在它之上構(gòu)建失敗指針剧罩？
我用一個例子給你講解。這里有 4 個模式串座泳，分別是 c惠昔，bc，bcd挑势，abcd镇防；主串是 abcd。

假設(shè)我們沿 Trie 樹走到 p 節(jié)點扑毡，也就是下圖中的紫色節(jié)點胃榕，那 p 的失敗指針就是從 root 走到紫色節(jié)點形成的字符串 abc，跟所有模式串前綴匹配的最長可匹配后綴子串瞄摊，就是箭頭指的 bc 模式串勤晚。

這里的最長可匹配后綴子串，我稍微解釋一下泉褐。字符串 abc 的后綴子串有兩個 bc赐写，c，我們拿它們與其他模式串匹配膜赃，如果某個后綴子串可以匹配某個模式串的前綴挺邀，那我們就把這個后綴子串叫作可匹配后子串。

我們從可匹配后綴子串中跳座，找出最長的一個端铛，就是剛剛講到的最長可匹配后綴子串。我們將 p 節(jié)點的失敗指針指向那個最長匹配后綴子串對應(yīng)的模式串的前綴的最后一個節(jié)點疲眷，就是下圖中箭頭指向的節(jié)點禾蚕。

計算每個節(jié)點的失敗指針這個過程看起來有些復(fù)雜。其實狂丝，如果我們把樹中相同深度的節(jié)點放到同一層换淆，那么某個節(jié)點的失敗指針只有可能出現(xiàn)在它所在層的上一層。

我們可以像 KMP 算法那樣几颜，當我們要求某個節(jié)點的失敗指針的時候倍试，我們通過已經(jīng)求得的、深度更小的那些節(jié)點的失敗指針來推導(dǎo)蛋哭。也就是說县习，我們可以逐層依次來求解每個節(jié)點的失敗指針。所以谆趾，失敗指針的構(gòu)建過程躁愿，是一個按層遍歷樹的過程。

首先 root 的失敗指針為 NULL沪蓬，也就是指向自己彤钟。當我們已經(jīng)求得某個節(jié)點 p 的失敗指針之后，如何尋找它的子節(jié)點的失敗指針呢怜跑？

我們假設(shè)節(jié)點 p 的失敗指針指向節(jié)點 q样勃，我們看節(jié)點 p 的子節(jié)點 pc 對應(yīng)的字符吠勘，是否也可以在節(jié)點 q 的子節(jié)點中找到。如果找到了節(jié)點 q 的一個子節(jié)點 qc峡眶，對應(yīng)的字符跟節(jié)點 pc 對應(yīng)的字符相同剧防，則將節(jié)點 pc 的失敗指針指向節(jié)點 qc。

如果節(jié)點 q 中沒有子節(jié)點的字符等于節(jié)點 pc 包含的字符辫樱，則令 q=q->fail（fail 表示失敗指針峭拘，這里有沒有很像 KMP 算法里求 next 的過程？）狮暑，繼續(xù)上面的查找鸡挠，直到 q 是 root 為止，如果還沒有找到相同字符的子節(jié)點搬男，就讓節(jié)點 pc 的失敗指針指向 root拣展。

public void buildFailurePointer() {
  Queue<AcNode> queue = new LinkedList<>();
  root.fail = null;
  queue.add(root);
  while (!queue.isEmpty()) {
    AcNode p = queue.remove();
    for (int i = 0; i < 26; ++i) {
      AcNode pc = p.children[i];
      if (pc == null) continue;
      if (p == root) {
        pc.fail = root;
      } else {
        AcNode q = p.fail;
        while (q != null) {
          AcNode qc = q.children[pc.data - 'a'];
          if (qc != null) {
            pc.fail = qc;
            break;
          }
          q = q.fail;
        }
        if (q == null) {
          pc.fail = root;
        }
      }
      queue.add(pc);
    }
  }
}

通過按層來計算每個節(jié)點的子節(jié)點的失效指針敦冬，剛剛舉的那個例子辅搬，最后構(gòu)建完成之后的 AC 自動機就是下面這個樣子：

我們還是拿之前的例子來講解。在匹配過程中夯缺，主串從 i=0 開始蚤氏，AC 自動機從指針 p=root 開始，假設(shè)模式串是 b踊兜，主串是 a。

• 如果 p 指向的節(jié)點有一個等于 b[i] 的子節(jié)點 x佳恬，我們就更新 p 指向 x捏境，這個時候我們需要通過失敗指針，檢測一系列失敗指針為結(jié)尾的路徑是否是模式串毁葱。這一句不好理解垫言，你可以結(jié)合代碼看。處理完之后倾剿，我們將 i 加一筷频，繼續(xù)這兩個過程蚌成；
• 如果 p 指向的節(jié)點沒有等于 b[i] 的子節(jié)點，那失敗指針就派上用場了凛捏，我們讓 p=p->fail担忧，然后繼續(xù)這 2 個過程。

關(guān)于匹配的這部分坯癣，文字描述不如代碼看得清楚瓶盛，所以我把代碼貼了出來，非常簡短示罗，并且添加了詳細的注釋惩猫，你可以對照著看下。這段代碼輸出的就是蚜点，在主串中每個可以匹配的模式串出現(xiàn)的位置轧房。

public void match(char[] text) { // text 是主串
  int n = text.length;
  AcNode p = root;
  for (int i = 0; i < n; ++i) {
    int idx = text[i] - 'a';
    while (p.children[idx] == null && p != root) {
      p = p.fail; // 失敗指針發(fā)揮作用的地方
    }
    p = p.children[idx];
    if (p == null) p = root; // 如果沒有匹配的，從 root 開始重新匹配
    AcNode tmp = p;
    while (tmp != root) { // 打印出可以匹配的模式串
      if (tmp.isEndingChar == true) {
        int pos = i-tmp.length+1;
        System.out.println(" 匹配起始下標 " + pos + "; 長度 " + tmp.length);
      }
      tmp = tmp.fail;
    }
  }
}