Java資料結構之AC自動機演演算法的實現

class AcNode {
    /**
     * 經過該節點的模式串的下層節點
     */
    Map<Character, AcNode> next = new HashMap<>();

    /**
     * 模式串的長度，也是節點的深度
     */
    int depth;

    /**
     * 失配指標，如果沒有匹配到，則跳轉到此狀態。
     */
    AcNode failure;

    public boolean hashNext(char nextKey) {
        return next.containsKey(nextKey);
    }

    public AcNode getNext(char nextKey) {
        return next.get(nextKey);
    }
}

/**
 * trie根節點
 */
private AcNode root;
/**
 * 加入模式串，構建Trie
 *
 * @param word 模式串，非空
 */
public void insert(String word) {
    AcNode cur = root;
    for (char c : word.toCharArray()) {
        if (!cur.next.containsKey(c)) {
            cur.next.put(c, new AcNode());
        }
        cur = cur.next.get(c);
    }
    cur.depth = word.length();
}

/**
 * 為所有節點構建失配指標，一個bfs層序遍歷
 */
public void buildFailurePointer() {
    ArrayDeque<AcNode> queue = new ArrayDeque<AcNode>();
    //將所有root的直接子節點的failure設定為root，並且加入queue
    for (AcNode acNode : root.next.values()) {
        acNode.failure = root;
        queue.addLast(acNode);
    }
    //bfs構建失配指標
    while (!queue.isEmpty()) {
        //父節點出佇列
        AcNode parent = queue.pollFirst();
        //遍歷父節點的下層子節點，基於父節點求子節點的失配指標
        for (Map.Entry<Character, AcNode> characterAcNodeEntry : parent.next.entrySet()) {
            //獲取父節點的失配指標
            AcNode pf = parent.failure;
            //獲取子節點
            AcNode child = characterAcNodeEntry.getValue();
            //獲取子節點對應的字元
            Character nextKey = characterAcNodeEntry.getKey();
            //如果pf節點不為null，並且pf節點的子節點對應的字元中，沒有包含了當前節點的所表示的字元
            while (pf != null && !pf.hashNext(nextKey)) {
                //繼續獲取pf節點的失配指標節點，繼續重複判斷
                pf = pf.failure;
            }
            //pf為null，表示找到了根節點，並且根節點的子節點也沒有匹配
            if (pf == null) {
                //此時直接將節點的失配指標指向根節點
                child.failure = root;
            }
            //pf節點的子節點對應的字元中，包含了當前節點的所表示的字元
            else {
                //節點的失配指標可以直接指向pf節點下的相同字元對應的子節點
                child.failure = pf.getNext(nextKey);
            }
            //最後不要忘了，將當前節點加入佇列
            queue.addLast(child);
        }
    }
}

/**
 * 匹配文字
 *
 * @param text 文字字串
 */
public List<ParseResult> parseText(String text) {
    List<ParseResult> parseResults = new ArrayList<>();
    char[] chars = text.toCharArray();
    //從根節點開始匹配
    AcNode cur = root;
    //遍歷字串的每個字元
    for (int i = 0; i < chars.length; i++) {
        //當前字元
        char nextKey = chars[i];
        //如果cur不為null，並且當前節點的的子節點不包括當前字元，即不匹配
        while (cur != null && !cur.hashNext(nextKey)) {
            //那麼通過失配指標轉移到下一個節點繼續匹配
            cur = cur.failure;
        }
        //如果節點為null，說明當前字元匹配到了根節點且失敗
        //那麼繼續從根節點開始進行下一輪匹配
        if (cur == null) {
            cur = root;
        } else {
            //匹配成功的節點
            cur = cur.getNext(nextKey);
            //繼續判斷
            AcNode temp = cur;
            while (temp != null) {
                //如果當前節點是某個關鍵詞的結尾，那麼取出來
                if (temp.depth != 0) {
                    int start = i - temp.depth + 1, end = i;
                    parseResults.add(new ParseResult(start, end, new String(chars, start, temp.depth)));
                    //System.out.println(start + " " + end + " " + new String(chars, start, temp.depth));
                }
                //繼續判斷該節點的失配指標節點
                //因為失配指標節點表示的模式串是當前匹配的模式串的在這些關鍵詞中的最長字尾，且由於當前節點的路徑包括了失配指標的全部路徑
                //並且失配指標路徑也是一個完整的關鍵詞，需要找出來。
                temp = temp.failure;
            }
        }
    }
    return parseResults;
}

class ParseResult {
    int startIndex;
    int endIndex;
    String key;

    public ParseResult(int startIndex, int endIndex, String key) {
        this.startIndex = startIndex;
        this.endIndex = endIndex;
        this.key = key;
    }

    @Override
    public String toString() {
        return "{" +
                "startIndex=" + startIndex +
                ", endIndex=" + endIndex +
                ", key='" + key + ''' +
                '}';
    }
}