詳解Java中AC自動機的原理與實現

public static class Node{
       //當前節點值
       private char value;
       //當前節點的孩子節點
       private Node[] childNode;
       //標誌當前節點是否是某單詞結尾
       private boolean isTail;
       //失敗指標
       private Node failNode;
       //匹配串長度，當isTail==true時，表示從root噹噹前位置是一個完整的匹配串，記錄這個匹配串的長度，便於之後快速找到匹配串
       private Integer tailLength;
       public Node(char value) {
           this.value = value;
      }
  }

Node root;
   public void init() {
       root = new Node('');
       root.childNode = new Node[26];
  }

public void insertStr(char[] chars) {
       //首先判斷首字元是否已經在字典樹中，然後判斷第二字元，依次往下進行判斷，找到第一個不存在的字元進行插入孩節點
       Node p = root;
       //表明當前處理到了第幾個字元
       int chIndex = 0;
       while (chIndex < chars.length) {
           while (chIndex < chars.length && null != p) {
               Node[] children = p.childNode;
               boolean find = false;
               for (Node child : children) {
                   if (null == child) {continue;}
                   if (child.value == chars[chIndex]) {
                       //當前字元已經存在，不需要再進行儲存
                       //從當前節點出發，儲存下一個字元
                       p = child;
                       ++ chIndex;
                       find = true;
                       break;
                  }
              }
               if (Boolean.TRUE.equals(find)) {
                   //在孩子中找到了 不用再次儲存
                   break;
              }
               //如果把孩子節點都找遍了，還沒有找到這個字元，直接將這個字元加入當前節點的孩子節點
               Node node = new Node(chars[chIndex]);
               node.childNode = new Node[26];
               children[chars[chIndex] - 'a'] = node;
               p = node;
               ++ chIndex;
          }
      }
       //字串中字元全部進入tire樹中後，將最後一個字元所在節點標誌為結尾節點
       p.isTail = true;
       p.tailLength = chars.length;
  }

public void madeFailNext() {
       //層序遍歷，為了保證求解這個節點失敗指標的時候，它的父節點的失敗指標以及失敗指標的失敗指標。。。。已經求得，可以完全根據這個找
       Deque<Node> nodes = new LinkedList<>();
       nodes.add(root);
       while (!nodes.isEmpty()) {
           Node current = nodes.poll();
           Node[] children = current.childNode;
           for (Node child : children) {
               if (null == child) {
                   continue;
              }
               Node failNode = current.failNode;
               while (null != failNode) {
                   //找到當前節點的失敗指標，檢視失敗指標子節點是否有==
                   Node[] failChildren = failNode.childNode;
                   Node node = failChildren[child.value - 'a'];
                   if (null == node) {
                       //找當前指標的下一個指標
                       failNode = failNode.failNode;
                       continue;
                  }
                   //已經找到匹配的
                   //將失敗指標指向node
                   child.failNode = node;
                   break;
              }
               //如果找完還沒有找到，指向root
               if (null == failNode) {
                   child.failNode = root;
              }
               nodes.add(child);
          }
      }
  }

/**
    * 匹配出str中所有出現的關鍵詞
    * @param str
    * @return
    */
   public List<String> match(String str) {
       //遍歷當前子串串，從根節點出發，如果匹配就一直往下進行匹配，同時需要看匹配的節點是否為結尾節點，如果是，匹配上一個
       //如果不匹配則通過失敗指標轉移到下一個節點
       this.dfs(root, 0, str);
       return machStr;
  }

   //abcdeasdabcebcd
   List<String> machStr = new ArrayList<>();
   private void dfs(Node node, int chIndex, String chars) {
       if (chIndex >= chars.length()) {
           return;
      }
       //從將當前字元與當前node的孩子節點進行匹配，如果當前字元與node的孩子節點.value匹配，判斷當前字元是否為尾節點，是，則記錄，匹配到了一個
       //繼續匹配（子節點，與下一個元素進行匹配）
       //如果不匹配，則轉到失敗指標
       Node[] children = node.childNode;
       Node child = children[chars.charAt(chIndex) - 'a'];
       if (null == child) {
           //不匹配，轉到失敗指標
           //如果當前node==root，從root匹配，root的失敗指標是null
           if (node == root) {
               dfs(root, ++ chIndex, chars);
          } else {
               dfs(node.failNode, chIndex, chars);
          }
      } else {
           //匹配到了
           if (child.isTail) {
               //並且是結尾節點，取從child.value到child.tailLength的字元
               machStr.add(chars.substring(chIndex - child.tailLength  + 1, chIndex + 1));
          }
           dfs(child, ++ chIndex, chars);
      }

  }

public static void main(String[] args) {
       ACAutomaton acAutomaton = new ACAutomaton();
       //初始化一個僅有根節點的字典樹
       acAutomaton.init();
       //構建Tire樹
       acAutomaton.insertStr("out".toCharArray());
       acAutomaton.insertStr("about".toCharArray());
       acAutomaton.insertStr("act".toCharArray());
       //構建失敗指標
       acAutomaton.madeFailNext();
       System.out.println("ces");
       //匹配
       List<String> result = acAutomaton.match("abcdeasactdaboutcebcd");
  }