Java实现基于Aho-Corasick算法的多模式回文串检测

Aho-Corasick算法是一种多模式字符串匹配算法，用于在文本中查找多个子字符串

import java.util.*;

public class AhoCorasick {
    private TrieNode root;
    private List<TrieNode> nodes;
    private Map<String, List<Integer>> patternPositions;

    public AhoCorasick() {
        root = new TrieNode();
        nodes = new ArrayList<>();
        patternPositions = new HashMap<>();
    }

    public void addPattern(String pattern) {
        TrieNode node = root;
        for (char c : pattern.toCharArray()) {
            if (!node.children.containsKey(c)) {
                node.children.put(c, new TrieNode());
            }
            node = node.children.get(c);
        }
        int index = nodes.size();
        node.isEndOfWord = true;
        nodes.add(node);
        patternPositions.computeIfAbsent(pattern, k -> new ArrayList<>()).add(index);
    }

    public List<Integer> searchPatterns(String text) {
        List<Integer> result = new ArrayList<>();
        TrieNode node = root;
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (!node.children.containsKey(c)) {
                node = root;
            } else {
                node = node.children.get(c);
            }
            if (node.isEndOfWord) {
                for (int patternIndex : patternPositions.getOrDefault(text.substring(i - node.length() + 1), Collections.emptyList())) {
                    result.add(patternIndex);
                }
            }
        }
        return result;
    }

    private static class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
        }
    }

    public static void main(String[] args) {
        AhoCorasick ac = new AhoCorasick();
        ac.addPattern("abc");
        ac.addPattern("def");
        ac.addPattern("ghi");
        System.out.println(ac.searchPatterns("abcdefghi")); // Output: [0, 3]
    }
}

这个实现中，我们首先创建了一个AhoCorasick类，其中包含一个TrieNode类来表示Aho-Corasick算法中的字典树节点。addPattern方法用于向字典树中添加模式字符串，searchPatterns方法用于在文本中查找所有匹配的模式字符串的位置。

在main方法中，我们创建了一个AhoCorasick实例，并添加了三个模式字符串。然后，我们在文本"abcdefghi"中查找这些模式字符串，并将结果输出到控制台。在这个例子中，输出结果为[0, 3]，表示模式字符串"abc"和"def"分别在文本中的位置0和3。