前缀树(Trie)暨hihocoder1014 python实现

前缀树trie详细解释查看hicodere 1014 的应用主要用于处理海量数据，统计出现最频繁的单词，以前根据前缀显示单词，通过共享前缀的方式节省空间和提升效率使用,查找单词的时间复杂度为O(nlength),空间复杂度小于O(nlength),在建立树的过程中，我们使用count来记录每个字符出现的次数，下面给出python代码:

class TrieNode:
    def __init__(self):
        self.nodes = collections.defaultdict(TrieNode)
        self.count = 1
        self.isword = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def add(self,word):
        curr = self.root
        for char in word:
            if char in curr.nodes:
                curr.nodes[char].count+=1
            curr = curr.nodes[char]
        curr.isword = True

    def search(self,word):
        curr = self.root
        for char in word:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return curr.isword

    def startWith(self,prefix):
        curr = self.root
        for char in prefix:
            if char not in curr.nodes:
                return 0
            curr = curr.nodes[char]
        return curr.count

trie = Trie()
while True:
    try:
        N = int(raw_input())
        for i in xrange(N):
            trie.add(raw_input())
        N = int(raw_input())
        for i in xrange(N):
            print trie.startWith(raw_input())
    except EOFError:
        gc.enable()
        break

后缀树