AC自动机

发表于   |   分类于   |   阅读次数

AC自动机的python实现。AC自动机是结合Trie树和KMP的多模式匹配的实现。相对于KMP只能处理单个单词的查找，AC自动机通过构建Trie树和其fail指针的方式来对当前匹配失败的字符进行下一步的匹配，减少了时间复杂度，加快程序运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
    class node:
    def __init__(self):
        self.fail=None
        self.isword=False
        self.next={}
        self.word=None

class ac_automatic:
    def __init__(self):
        self.root = node()
        
    def add(self, word):
        p = self.root
        for w in word:
            if w in p.next:
                p = p.next[w]
            else:
                p.next[w] = node()
                p = p.next[w]
        p.isword=True
        p.word=word
    
    def judge(self):
        p = self.root
        temp = [p]
        
        
        while len(temp) != 0:
            d = temp.pop(0)
            for v in d.next.keys():
                p = d
                if p == self.root:
                    v.fail = self.root
                else:

                    while p.fail != None and v not in p.fail.next:
                        p = p.fail

                    if v in p.fail.next:
                        v.fail = p.fail.next[v]
                    else:
                        v.fail = self.root
            temp.append(v)
    def search(self, content):
        p = self.root
        final = []
        for w in content:

            while p.fail != None and w not in p.fail.next:
                p = p.fail

            if w in p.next:
                p = p.next[w]
            else:
                p = self.root
                
                
            if p.isword == True:
                final.append(p.word)
        return final

model = ac_automatic()
model.add("her")
model.add("she")
print(model.search("dfadooudashefhe2fdl"))