编写一个AC算法的实例

AC算法（Aho-Corasick算法）是一种多模式匹配算法，用于在一个文本串中查找多个模式串出现的位置。下面是一个AC算法的实例（Python实现）：

class ACNode:
    def __init__(self):
        self.next = {}
        self.fail = None
        self.word = None

class ACAutomaton:
    def __init__(self):
        self.root = ACNode()

    def add_pattern(self, pattern):
        node = self.root
        for c in pattern:
            if c not in node.next:
                node.next[c] = ACNode()
            node = node.next[c]
        node.word = pattern

    def build(self):
        queue = []
        for c, node in self.root.next.items():
            node.fail = self.root
            queue.append(node)
        while queue:
            rnode = queue.pop(0)
            for c, node in rnode.next.items():
                queue.append(node)
                fail_node = rnode.fail
                while fail_node and c not in fail_node.next:
                    fail_node = fail_node.fail
                node.fail = fail_node.next[c] if fail_node else self.root
                node.word = node.fail.word if node.fail.word else node.word

    def search(self, text):
        res = []
        p = self.root
        for i, c in enumerate(text):
            while p != self.root and c not in p.next:
                p = p.fail
            if c in p.next:
                p = p.next[c]
            else:
                p = self.root
            if p.word:
                res.append((i - len(p.word) + 1, p.word))
        return res

使用方法如下：

ac = ACAutomaton()
patterns = ['he', 'she', 'his', 'hers']
for p in patterns:
    ac.add_pattern(p)
ac.build()
text = 'ushershehis'
res = ac.search(text)
print(res)  # [(4, 'she'), (6, 'his'), (9, 'he')]

这个例子中，我们首先创建了一个AC自动机，然后向它添加了4个模式串。调用`build`方法构建AC自动机后，就可以使用`search`方法在文本串中查找模式串出现的位置。