AcWing 835. Trie字符串统计
原题链接
简单
作者:
arthur15
,
2019-09-07 22:17:23
,
所有人可见
,
阅读 841
python3代码
class Tire():
def __init__(self):
self.tire = [0, {}] # [1, {'c': [0, {'a': [0, {'b': [0, {'d': [1, {}]}]}]}]}]
def insert(self, word):
p = self.tire
for w in word:
if w not in p[1]:
p[1][w] = [0, {}]
p = p[1][w]
p[0] += 1 # 给终止的地方打一个标记
def query(self, word):
p = self.tire
for w in word:
if w not in p[1]:
return 0
else:
p = p[1][w]
return p[0] # 返回这个长度的字符串, 打一个标记
if __name__ == '__main__':
n = int(input())
T = Tire()
while n > 0:
op, word = input().split()
if op == 'I':
T.insert(word)
else:
print(T.query(word))
n -= 1