原理

把所有的映射构建一个Tire树，然后用ac自动机匹配替换

代码

public class AhoCorasickAutomaton {

    /*AC自动机的根结点，根结点不存储任何字符信息*/
    private final Node root;

    /*待查找的目标字符串集合*/
    private final Map<String, String> target;

    /**
     * @param target 待查找的目标字符串集合
     */
    public AhoCorasickAutomaton(Map<String, String> target) {
        root = new Node();
        this.target = target;
        buildTrieTree();
        buildAcFromTrie();
    }

    /**
     * 用于表示AC自动机的每个结点，在每个结点中我们并没有存储该结点对应的字符
     */
    private static class Node {

        /*如果该结点是一个终点，即，从根结点到此结点表示了一个目标字符串，则str != null, 且str就表示该字符串*/
        String str;

        /*该节点下的子节点*/
        Map<Character, Node> children = new HashMap<>();

        /*当前结点的孩子结点不能匹配文本串中的某个字符时，下一个应该查找的结点*/
        Node fail;

        public boolean isWord() {
            return str != null;
        }

    }

    /**
     * 由目标字符串构建Trie树
     */
    private void buildTrieTree() {
        for (String targetStr : target.keySet()) {
            Node curr = root;
            if (targetStr == null) {
                continue;
            }
            for (int i = 0; i < targetStr.length(); i++) {
                char ch = targetStr.charAt(i);
                Node node = curr.children.get(ch);
                if (node == null) {
                    node = new Node();
                    curr.children.put(ch, node);
                }
                curr = node;
            }
            /*将每个目标字符串的最后一个字符对应的结点变成终点*/
            curr.str = targetStr;
        }
    }

    /**
     * 由Trie树构建AC自动机，本质是一个自动机，相当于构建KMP算法的next数组
     */
    private void buildAcFromTrie() {
        /*广度优先遍历所使用的队列*/
        LinkedList<Node> queue = new LinkedList<>();

        /*单独处理根结点的所有孩子结点*/
        for (Node x : root.children.values()) {
            /*根结点的所有孩子结点的fail都指向根结点*/
            x.fail = root;
            queue.addLast(x);/*所有根结点的孩子结点入列*/
        }

        while (!queue.isEmpty()) {
            /*确定出列结点的所有孩子结点的fail的指向*/
            Node p = queue.removeFirst();
            for (Map.Entry<Character, Node> entry : p.children.entrySet()) {

                /*孩子结点入列*/
                queue.addLast(entry.getValue());
                /*从p.fail开始找起*/
                Node failTo = p.fail;
                while (true) {
                    /*说明找到了根结点还没有找到*/
                    if (failTo == null) {
                        entry.getValue().fail = root;
                        break;
                    }

                    /*说明有公共前缀*/
                    if (failTo.children.get(entry.getKey()) != null) {
                        entry.getValue().fail = failTo.children.get(entry.getKey());
                        break;
                    } else {/*继续向上寻找*/
                        failTo = failTo.fail;
                    }
                }

            }
        }
    }

    /**
     * 在文本串中替换所有的目标字符串
     *
     * @param text          被替换的目标字符串
     * @param stringBuilder 替换后的结果
     */
    public void replace(CharSequence text, StringBuilder stringBuilder) {
        Node curr = root;
        int i = 0;
        while (i < text.length()) {
            /*文本串中的字符*/
            char ch = text.charAt(i);
            /*文本串中的字符和AC自动机中的字符进行比较*/
            Node node = curr.children.get(ch);
            if (node != null) {
                stringBuilder.append(ch);
                /*若相等，自动机进入下一状态*/
                curr = node;
                if (curr.isWord()) {
                    stringBuilder.delete(stringBuilder.length() - curr.str.length(), stringBuilder.length());
                    stringBuilder.append(target.get(curr.str));
                    curr = root;
                }
                /*索引自增，指向下一个文本串中的字符*/
                i++;
            } else {
                /*若不等，找到下一个应该比较的状态*/
                curr = curr.fail;
                /*到根结点还未找到，说明文本串中以ch作为结束的字符片段不是任何目标字符串的前缀，状态机重置，比较下一个字符*/
                if (curr == null) {
                    stringBuilder.append(ch);
                    curr = root;
                    i++;
                }
            }
        }
    }

}