字符串匹配算法之 AC 自動機

我們經常用的字符串方法indexOf，都是判定兩個字符串的包含關係，底層使用類似KMP，BM， Sunday這樣的算法。如果我們要判斷一個長字符串是否包含多個短字符串呢？比如在一篇文章找幾個敏感詞，在DNA串中找幾個指定的基因對pattern進行預處理，如果我們的模式串存在多個，則不適合了，我們就需要用到一種多模式匹配算法。

最著名的多模式匹配算法為AC自動機，它是由貝爾實驗室的兩位研究人員 Alfred V. Aho 和 Margaret J.Corasick 於1975年發明的，幾乎與KMP算法同時問世，至今日仍然在模式匹配領域被廣泛應用。

AC自動機的核心算法仍然是尋找模式串內部規律，達到在每次失配時的高效跳轉。這一點與單模式匹配KMP算法是一致的。不同的是，AC算法尋找的是模式串之間的相同前綴關係。

在KMP算法中，對於模式串」abcabcacab」，我們知道非前綴子串abc(abca)cab是模式串的一個前綴(abca)bcacab，而非前綴子串ab(cabca)cab不是模式串abcabcacab的前綴，根據此點，我們構造了next數組，實現在匹配失敗時的跳轉。

而在多模式環境中，AC自動是使用前綴樹來存放所有模式串的前綴，然後通過失配指針來處理失配的情況。它大概分為三個步驟：構建前綴樹（生成goto表），添加失配指針（生成fail表），模式匹配（構造output表）。下面，我們拿模式集合[say, she, shr, he, her]為例，構建一個AC 自動機。

構建前綴樹

將模式串逐字符放進Trie樹。

class Trie {
      constructor() {
          this.root = new Node("root");
      }
      insert(word) {
          var cur = this.root;
          for (var i = 0; i < word.length; i++) {
              var c = word[i];
              var node = cur.children[c];
              if (!node) {
                  node = cur.children[c] = new Node(word[i]);
              }
              cur = node;
          }
          cur.pattern = word; //防止最後收集整個字符串用
          cur.endCount++; //這個字符串重複添加的次數
      }
  }
  function createGoto(trie, patterns) {
      for (var i = 0; i < patterns.length; i++) {
          trie.insert(patterns[i]);
      }
  }
然後我們嘗試用它處理字符串sher。理想情況下是這樣：
很遺憾，前綴樹只會順著某一路逕往下查找，最多到葉子節點折回樹節點，繼續選擇另一條路徑。因此我們需要添加一些橫向的路徑，在失配時，跳到另一個分支上繼續查找，保證搜索過的節點不會冗餘搜索。
添加失配指針
AC自動機的前綴樹的節點都應該存在fail指針。下圖中，紅色的箭頭就是失配指針。它表示文本串在當前節點失配後，我們應該到哪個節點去繼續匹配。
很顯然，對於每個節點，其失配指針應該指向其他子樹中的表示同一字符的那些節點，並且它與其子樹能構成剩下的最長後綴。即，我們要匹配sher, 我們已經在某一子樹中命中了sh，那麼我們希望能在另一個子樹中命中er。
到這裡，你是不是發現fail指針和KMP中的next指針簡直一毛一樣？它們都被稱為「失配指針」。將Trie樹上的每一個點都加上fail指針，它就變成了AC自動機。AC自動機其實就是Trie + KMP。
因此根據補上一些失配指針，我們的AC自動機應該長成這樣的。
現在的問題是，如何求fail指針？聯繫KMP算法的next數組的意義，容易發現root的每個兒子的fail都指向root（前綴和後綴是不會包含整個串的）。也就是上圖中root所連的s和h的fail都指向root。若已經求得sh所在點的fail，我們來考慮如何求she所在點的fail。根據sh所在點的fail得到h是sh的最長後綴，而h又有兒子e，因此she的最長後綴應該是he，其fail指針就指向he所在點。
概括AC自動機求fail指針的過程：
1.對整個字典樹進行寬度優先遍歷。
2.若當前搜索到點x，那麼對於x的第i個兒子(也就是代表字符i的兒子)，一直往x的fail跳，直到跳到某個點也有i這個兒子，x的第i個兒子的fail就指向這個點的兒子i。
function createFail(ac) {
    var root = ac.root;
    var queue = [root]; //root所在層為第0層
    while (queue.length) {
        //廣度優先遍歷
        var node = queue.shift();
        if (node) {
            //將其孩子逐個加入列隊
            for (var i in node.children) {
                var child = node.children[i];
                if (node === root) {
                    child.fail = root; //第1層的節點的fail總是指向root
                } else {
                    var p = node.fail; //第2層以下的節點, 其fail是在另一個分支上
                    while (p) {
                        //遍歷它的孩子，看它們有沒與當前孩子相同字符的節點
                        if (p.children[i]) {
                            child.fail = p.children[i];
                            break;
                        }
                        p = p.fail;
                    }
                    if (!p) {
                        child.fail = root;
                    }
                }
                queue.push(child);
            }
        }
    }
}
模式匹配
我們從根節點開始查找，如果它的孩子能命中目標串的第1個字符串，那麼我們就從這個孩子的孩子中再嘗試命中目標串的第2個字符串。否則，我們就順著它的失配指針，跳到另一個分支，找其他節點。
如果都沒有命中，就從根節點重頭再來。
當我們節點存在表示有字符串在它這裡結束的標識時（如endCound, isEnd），我們就可以確認這字符串已經命中某一個模式串，將它放到結果集中。如果這時長字符串還沒有到盡頭，我們繼續收集其他模式串。
代碼如下：
function match(ac, text) {
    var root = ac.root, p = root, ret = [], unique = {};
    for (var i = 0; i < text.length; i++) {
        var c = text[i];
        while (!p.children[c] && p != root) {
            p = p.fail; // 失配指針發揮作用 by 司徒正美
        }
        p = p.children[c];
        if (!p) {
            p = root; // 如果沒有匹配的，從 root 開始重新匹配
        }
        var node = p;
        while (node != root) {
            //  收集出可以匹配的模式串
            if (node.endCount) {
                var pos = i - node.pattern.length + 1;
                console.log(`匹配模式串 ${node.pattern}其起始位置在${pos}`)
                if (!unique[node.pattern]) { //by 司徒正美
                    unique[node.pattern] = 1;
                    ret.push(node.pattern);
                }
            }
            node = node.fail;
        }
    }
    return ret;
}

var ac = new Trie();
createGoto(ac, ["she", "shr", "say", "he", "her"]);
createFail(ac);
console.log(match(ac, "one day she say her has eaten many shrimps"));