Java實(shí)現(xiàn)基于Aho-Corasick算法的多模式回文串檢測

Aho-Corasick算法是一種多模式字符串匹配算法，用于在文本中查找多個(gè)子字符串

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]
    }
}

這個(gè)實(shí)現(xiàn)中，我們首先創(chuàng)建了一個(gè)AhoCorasick類，其中包含一個(gè)TrieNode類來表示Aho-Corasick算法中的字典樹節(jié)點(diǎn)。addPattern方法用于向字典樹中添加模式字符串，searchPatterns方法用于在文本中查找所有匹配的模式字符串的位置。

在main方法中，我們創(chuàng)建了一個(gè)AhoCorasick實(shí)例，并添加了三個(gè)模式字符串。然后，我們在文本"abcdefghi"中查找這些模式字符串，并將結(jié)果輸出到控制臺。在這個(gè)例子中，輸出結(jié)果為[0, 3]，表示模式字符串"abc"和"def"分別在文本中的位置0和3。