前綴樹trie詳細解釋查看hicodere 1014 的應(yīng)用主要用于處理海量數(shù)據(jù)，統(tǒng)計出現(xiàn)最頻繁的單詞徐许，以前根據(jù)前綴顯示單詞，通過共享前綴的方式節(jié)省空間和提升效率使用,查找單詞的時間復(fù)雜度為O(nlength),空間復(fù)雜度小于O(nlength),在建立樹的過程中猾蒂，我們使用count來記錄每個字符出現(xiàn)的次數(shù)幌羞，下面給出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
后綴樹
