Aho-Corasick automation，AC 自动机

构造 AC 自动机分两步：第一步构造 Trie 树比较简单；第二步给 Trie 树的每个结点加 fail 边。给一个结点添加 fail 边时，从其父结点开始沿 fail 边开始搜索，直到找到一个匹配结点（即 p.next[c] != null 的结点，c 为当前字符），或者找到根结点，fail 边即指向找到的匹配结点或根结点，递推时按照 Trie 树的层次遍历，保证访问到某结点时其父结点的 fail 边都已经定义。查询时，对顺序读入的每个字符，从当前结点开始沿 fail 边查找匹配结点（如果当前结点匹配则返回当前结点，如果不匹配则沿 fail 边查下一个结点），这样可以找到一个匹配结点或者找到根结点。找到匹配结点后，从匹配结点开始沿 fail 边遍历到根结点，遍历过程中遇到的每个模式结束点都对应一个匹配模式。
import java.util.HashMap;

public class ACAutomation {

private static int KIND = 26;
private static int SIZE = 1024;

private class Node {
  public int count;  //在本结点结束的模式串数目，0表示非结束结点
  public Node fail;  //失配指针
  public Node[] next;  //子结点指针
  public Node() {
   count = 0;
   fail = null;
   next = new Node[KIND];
  }
}

private Node root = new Node();

public ACAutomation(String[] strs) {
   buildTrie(strs);
   buildFail();
}

private int index(char c) {
  return c - 'a';
}

// 从模式字符串数组构造Trie树
private void buildTrie(String[] strs) {
  for ( String str : strs ) {
   insert(str);
  }
}

// 向Trie树中添加一个模式字符串
private void insert(String str) {
  Node node = root;
  for ( int i=0; i<str.length(); i++ ) {
   int idx = index(str.charAt(i));
   if ( node.next[idx] == null )
    node.next[idx] = new Node();
   node = node.next[idx];
  }
  node.count++;
}

// 基于Trie树构造AC自动机，添加fail边
private void buildFail() {
  Node[] queue = new Node[SIZE];
  int head=0, tail=0;
  queue[(tail++)%SIZE] = root;
  while ( tail != head ) {
   //从队列取出一个父结点
   Node parent = queue[(head++)%SIZE];
   for ( int i=0; i<KIND; i++ ) {
    Node child = parent.next[i];
    if ( child != null ) {
     //对每一个子结点更新fail
     Node match = parent.fail;
     while ( match != null && match.next[i] == null )
      match = match.fail;
     child.fail=(match!=null)?match.next[i]:root;
     //对每一个子结点进栈
     queue[(tail++)%SIZE] = child;
    }
   }
  }
}

// 查询和输入串 str 匹配的所有模式串，同一模式串每次匹配都计数
public int query(String str) {
  Node p = root;
  int count = 0;
  for ( int i=0; i<str.length(); i++ ) {
   int idx = index(str.charAt(i));
   // 查找下一个匹配结点即 p.next[idx] 不为 null 的结点
   while ( p != null && p.next[idx] == null ) p = p.fail;
   p = (p==null)?root:p.next[idx];
   // 从匹配结点开始沿fail找所有匹配模式串
   Node temp = p;
   while ( temp != null ) {
    if ( temp.count > 0 ) count++;
    temp = temp.fail;
   }
  }
  return count;
}

// 用于调试，打印Trie树AC自动机
private void print() {
  Node[] queue = new Node[SIZE];
  int head=0, tail=0;
  queue[(tail++)%SIZE] = root;
  HashMap<Node,Integer> map = new HashMap<Node,Integer>();
  while ( tail != head ) {
   //从队列取出一个父结点
   Node parent = queue[(head++)%SIZE];
   map.put(parent, head-1);
   System.out.printf("%d : fail(%s) count(%d)",head-1,map.get(parent.fail),parent.count);
   System.out.print('[');
   for ( int i=0; i<KIND; i++ ) {
    Node child = parent.next[i];
    if ( child != null ) {
     queue[(tail++)%SIZE] = child;
     System.out.printf("%c(%d)",'a'+i,tail-1);
    }

   }
   System.out.println(']');
  }
}

/**
* @param args
*/
public static void main(String[] args) {
  String[] strs = { "say", "she", "shr", "he", "her", "h" };
  ACAutomation auto = new ACAutomation(strs);
  auto.print();
  int r = auto.query("yasherhs");
  System.out.println(r);
}

}

补充：综合编程 , 其他综合 ,