前言
Aho Corasick Algorithm又叫AC自动机，该算法是一个匹配算法，用来匹配文本Text中多个patterns分别出现的次数；
我们定义n为patterns的总长度；m为Text的长度；
问题：在ahishershe文本中找出以下"he", "she", "hers", "his"各个patterns出现的次数；
最直接的暴力解法时间时间复杂度为O(n*m)，如果采用KMP Algorithm，会把时间度降低为O(n+m)，但是这是在单一的pattern的情况下，在k个pattern的情况下，应该成倍的增长m，时间复杂度为O(n+k*m)，使用Aho Corasick Algorithm可以把时间优化为O(n+m+z)，其中z表示出现的次数；
介绍
AC自动机利用的前缀树Trie这一数据结构；前缀树是一种很简单的结构，其构造如下：
我们可以构建Trie然后使用窗口进行暴力搜索，其时间复杂度为O(m*max(L))，这里面的max(L)是Trie的深度；
这里面可以优化的一个点是，我们可以利用不匹配词的最长后缀作为词的前缀去优化查找，而不是不匹配就重新从root开始；找到最长的公共后缀将保证我们不需要再次检查那么多字符串，并且在每次不匹配之后我们都会重复上一步骤；
这些指向最长后缀的节点的链接被称为suffix links或failure links，在匹配不成功的时候，若有最长的后缀节点，指向最长的后最节点，若没有则指向root进行重新查找；
假设在一颗Trie上有字符串w,x,...，其中x是w的最长的后缀，所以有红线连接w和a，若存在wa和xa，这xa也是wa的最长后缀，也用红线连接；
若xa不存在，就去找除了x以外的和w的最大公共后缀，如果发现y符合条件，可以对y进行匹配；如果y不符合条件，就接着找除了x,y以外的和w的最大公共后缀，依次进行；
其次需要优化的一点输出环节，如果pattern1是pattern2的后缀的情况下，我们可能会忽略掉pattern1，所以在寻找最大后缀时需要进行判断，如果最大后缀结点是pattern，就用output link连接原结点指向该结点，在以该结点为原结点去连接，直到root；如果不是就判断该结点的最大后缀结点是否是pattern，再用原结点去连接这一个结点；
在文本sting中，遍历到i的时候，可以发现sti的最大后缀ti并不是pattern，于是就找ti的最大后缀i，是pattern，于是用蓝色的线把sti和i结合起来；这里加粗了这一过程；
在遍历到n的时候，发现tin和in都是pattern，依次进行连接
这时时间复杂度为O(m+z)，其中z表示pattern的出现次数；
from collections import defaultdict class ahocorasick: def __init__(self, words): self.max_states = sum([len(word) for word in words]) self.max_characters = 26 self.out = [0] * (self.max_states + 1) self.fail = [-1] * (self.max_states + 1) self.goto = [[-1] * self.max_characters for _ in range(self.max_states + 1)] for i in range(len(words)): words[i] = words[i].lower() self.words = words self.states_count = self.__build_matching_machine() def __build_matching_machine(self): k = len(self.words) states = 1 for i in range(k): word = self.words[i] current_state = 0 for character in word: ch = ord(character) - 97 if self.goto[current_state][ch] == -1: self.goto[current_state][ch] = states states += 1 current_state = self.goto[current_state][ch] self.out[current_state] |= (1 << i) for ch in range(self.max_characters): if self.goto[0][ch] == -1: self.goto[0][ch] = 0 queue = [] for ch in range(self.max_characters): if self.goto[0][ch] != 0: self.fail[self.goto[0][ch]] = 0 queue.append(self.goto[0][ch]) while queue: state = queue.pop(0) for ch in range(self.max_characters): if self.goto[state][ch] != -1: failure = self.fail[state] while self.goto[failure][ch] == -1: failure = self.fail[failure] failure = self.goto[failure][ch] self.fail[self.goto[state][ch]] = failure self.out[self.goto[state][ch]] |= self.out[failure] queue.append(self.goto[state][ch]) return states def __find_next_state(self, current_state, next_input): answer = current_state ch = ord(next_input) - 97 while self.goto[answer][ch] == -1: answer = self.fail[answer] return self.goto[answer][ch] def search_words(self, text): text = text.lower() current_state = 0 result = defaultdict(list) for i in range(len(text)): current_state = self.__find_next_state(current_state, text[i]) if self.out[current_state] == 0: continue for j in range(len(self.words)): if (self.out[current_state] & (1 << j)) > 0: word = self.words[j] result[word].append(i - len(word) + 1) return result if __name__ == "__main__": words = ["he", "she", "hers", "his"] text = "ahishershe" aho_chorasick = ahocorasick(words) result = aho_chorasick.search_words(text) for word in result: for i in result[word]: print("Word", word, "appears from", i, "to", i + len(word) - 1)
