字符串匹配算法

單模式串匹配算法

是在一個模式串和一個主串之間進行匹配女坑，也就是說股囊，在一個主串中查找一個模式串宿亡。

多模式串匹配算法

就是在多個模式串和一個主串之間做匹配凑耻，也就是說，在一個主串中查找多個模式串攒钳。

經(jīng)典的多模式串匹配算法：AC自動機

AC自動機算法帮孔，全稱是Aho-Corasick算法。其實不撑，Trie樹跟AC自動機之間的關(guān)系文兢，就像單串匹配中樸素的串匹配算法，跟KMP算法之間的關(guā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; // 當(dāng)isEndingChar=true時，記錄模式串長度
  public AcNode fail; // 失敗指針
  public AcNode(char data) {
    this.data = data;
  }
}

所以幢妄，AC 自動機的構(gòu)建兔仰，包含兩個操作：

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

代碼

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; // 當(dāng)isEndingChar=true時乎赴，記錄模式串長度
  public AcNode fail; // 失敗指針
  public AcNode(char data) {
    this.data = data;
  }
}

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);
    }
  }
}

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("匹配起始下標(biāo)" + pos + "; 長度" + tmp.length);
      }
      tmp = tmp.fail;
    }
  }
}