“和谐” - 多模式匹配算法 - AC自动机

/** 把字典通过insert把所有单词插入Trie树，
 * 然后通过setSuffix()构建出对应的Trie图，
 * 然后从Trie图的根节点开始，沿着文章str的每一个字符，走出对应的边，
 * 直到遇到一个标记结点或者整个str都遍历完成
 */
public static class Trie {
    private TrieNode trie;
    Queue<TrieNode> queue;

    public Trie() {
        trie = new TrieNode(null, ' ');
        queue = new LinkedList<>();
    }

    public void insert(String word) {
        TrieNode curNode = trie;
        for (char x : word.toCharArray()) {
            curNode = insert(curNode, x);
        }
        curNode.setLast(true);
    }

    /** insert char x, means create a new node in the x edge.
     * return created node  */
    private TrieNode insert(TrieNode node, char x) {
        if (node.get(x) == null) {
            node.set(x);
        }
        return node.get(x);
    }

    /** BFS on the trie */
    public void setSuffix() {
        queue.add(trie);
        while (!queue.isEmpty()) {
            /** poll() removes the present head.
             http://www.tutorialspoint.com/java/util/linkedlist_poll.htm */
            TrieNode node = queue.poll();
            setSuffix(node);
            complementDFA(node);
        }
    }

    /** Set node's suffix, complement lacking edge
     * */
    private TrieNode setSuffix(TrieNode node) {
        if (node.root == null) { // Trie root
            node.suffix = node;
        } else if (node.root.root == null) {
            node.suffix = node.root.suffix;
        } else {
            node.suffix = node.root.suffix.get(node.fromIndex);
        }

        if (node.suffix.isLast) {
            node.isLast = true;
        }

        return node.suffix;
    }

    /** Complement DFA according to suffix */
    private void complementDFA(TrieNode node) {
        if (node.isLast) { return; }
        for (int i = 0; i < node.edges.length; i++) {
            if (node.edges[i] == null) {
                if (node.root == null) {
                    node.edges[i] = node;
                } else {
                    node.edges[i] = node.suffix.edges[i];
                }
            } else {
                queue.add(node.edges[i]);
            }
        }
    }

    public boolean search(String s) {
        boolean contains = false;
        TrieNode curNode = trie;
        for (int i = 0; i < s.length(); i++) {
            char x = s.charAt(i);
            curNode = curNode.get(x);
            if (curNode.isLast) {
                contains = true;
                break;
            }
        }
        return contains;
    }

    public static class TrieNode {
        static final int R = 26;
        static final int ATO0 = 97;
        boolean isLast;
        TrieNode[] edges;
        TrieNode root;
        char fromIndex;
        TrieNode suffix;

        public TrieNode(TrieNode root, char from) {
            this.root = root;
            fromIndex = from;
            edges = new TrieNode[R];
            isLast = false;
        }

        public TrieNode get(char ch) {
            return edges[ch - ATO0];
        }

        /** instantiate the ch child in edges */
        public void set(char ch) {
            edges[ch - ATO0] = new TrieNode(this, ch);
        }

        public void setLast(boolean isLast) {
            this.isLast = isLast;
        }

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Trie t = new Trie();
        String[] X = {"sb", "dsb", "cjdsb", "qnmlgb"};
        for (String x : X) {
            t.insert(x);
        }

        t.setSuffix();
        String s = "aadbaaadaaac";

        if (t.search(s)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

}