前缀树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
后缀树
