class Node:
def __init__(self):
self.fail = None # fail pointer: point to the longest suffix of the current node
self.next = {}
self.end = False
self.word = None
class AcAutomaton:
def __init__(self):
self.root = Node()
self.queue = []
def insert(self, word):
node = self.root
for char in word:
if char not in node.next:
node.next[char] = Node()
node = node.next[char]
node.end = True
node.word = word
def build(self):
self.queue.append(self.root)
while self.queue:
p = self.queue.pop(0)
for char, child in p.next.items():
if child is None:
continue
if p == self.root:
child.fail = self.root
else:
q = p.fail
while q:
if char in q.next:
child.fail = q.next[char]
break
q = q.fail
if not q:
child.fail = self.root
self.queue.append(child)
def match(self, text):
res = []
p = self.root
for char in text:
while char not in p.next and p != self.root:
p = p.fail
p = p.next.get(char, self.root)
tmp = p
while tmp != self.root:
if tmp.end:
res.append(tmp.word)
tmp = tmp.fail
return res
if __name__ == '__main__':
ac = AcAutomaton()
for word in ['he', 'she', 'hers', 'his']:
ac.insert(word)
ac.build()
print(ac.match('ahishers'))
