基于trie树做一个ac自动机

---

#!/usr/bin/python

# -*- coding: utf-8 -*-

class Node:

    def __init__(self):

        self.value = None

        self.children = {}  # children is of type {char, Node}

        self.fre = 0

        self.father = None

        self.fail = None

def CMP(a, b):

    return b.fre - a.fre

class Trie:

    def __init__(self):

        self.root = Node()

        self.choose = []

        self.__OpenCorrect__ = 0

    def insert(self, key):  # key is of type string

        # key should be a low-case string, this must be checked here!

        node = self.root

        for char in key:

            if char not in node.children:

                child = Node()

                node.children[char] = child

                child.value = char

                child.father = node

                node = child

            else:

                node = node.children[char]

        # node.value = key

        node.fre += 1

    def find_node(self, string):

        res_node = self.root

        try:

            for i in string:

                res_node = res_node.children[i]

        except:

            res_node = None

        return res_node

    def buildac3(self):

        queuelist = []

        queuelist.append(self.root)

        while len(queuelist) > 0:

            temp = queuelist.pop()

            p = None

            for k, v in temp.children.items():

                if temp == self.root:

                    temp.children[k].fail = self.root

                else:

                    p = temp.fail

                    while p is not None:

                        if p.children.has_key(k):

                            temp.children[k].fail = p.children[k]

                            break

                        p = p.fail

                    if p is None:

                        temp.children[k].fail = self.root

                queuelist.append(temp.children[k])

    def acfind(self, content):

        count = 0

        content2 = content

        while len(content2) > 1:

            p = self.root

            result = []

            startWordIndex = 0

            endWordIndex = -1

            currentPosition = 0

            while currentPosition < len(content2):

                word = content2[currentPosition]

                while p.children.has_key(word) == False and p != self.root:

                    p = p.fail

                if p.children.has_key(word):

                    if p == self.root:

                        startWordIndex = currentPosition

                    p = p.children[word]

                else:

                    p = self.root

                if p.fre > 0 and currentPosition - startWordIndex < len(content) - 1:

                    result.append((startWordIndex + count, currentPosition + count))

                currentPosition += 1

            for i in result:

                print content[i[0]:i[1] + 1]

            print result

            count += 1

            content2 = content2[1:]

if __name__ == '__main__':

    trie = Trie()

    trie.__OpenCorrect__ = 1

    trie.insert("she")

    trie.insert("he")

    trie.insert("her")

    trie.insert("hers")

    trie.buildac3()

    # print trie.find_node('sw')

    # print trie.root.children['s'].children['h'].fail.value

    print trie.acfind('shers')