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 + '\'' +
                '}';
    }
}