Aho-Corasick的实现时间太长了

class AhoCorasick:
    def __init__(self):
        self.trie = {}
        self.output = {}
        self.fail = {}

    def add_word(self, word):
        node = self.trie
        for char in word:
            node = node.setdefault(char, {})
        node['$'] = word

    def build(self):
        from collections import deque
        queue = deque()
        for key in self.trie:
            self.fail[key] = self.trie
            queue.append(self.trie[key])
        while queue:
            current_node = queue.popleft()
            for key, child in current_node.items():
                if key == '$':
                    continue
                fail_node = self.fail[current_node]
                while fail_node and key not in fail_node:
                    fail_node = self.fail[fail_node]
                self.fail[child] = fail_node[key] if fail_node else self.trie
                queue.append(child)

    def search(self, text):
        node = self.trie
        results = []
        for i, char in enumerate(text):
            while node and char not in node:
                node = self.fail[node]
            if not node:
                node = self.trie
                continue
            node = node[char]
            if '$' in node:
                results.append((i - len(node['$']) + 1, node['$']))
        return results

# 使用示例
ac = AhoCorasick()
patterns = ["he", "she", "his", "hers"]
for pattern in patterns:
    ac.add_word(pattern)
ac.build()
text = "ushers"
print(ac.search(text))  # 输出: [(1, 'she'), (2, 'he'), (2, 'hers')]

pip install pyahocorasick

import ahocorasick

A = ahocorasick.Automaton()
patterns = ["he", "she", "his", "hers"]
for idx, key in enumerate(patterns):
    A.add_word(key, (idx, key))
A.make_automaton()

text = "ushers"
for end_index, (insert_order, original_value) in A.iter(text):
    start_index = end_index - len(original_value) + 1
    print((start_index, original_value))