trie.py
1.15 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# -*- coding: utf-8 -*-
from __future__ import unicode_literals
class Trie(object):
def __init__(self):
self.d = {}
def insert(self, key, value):
now = self.d
for k in key:
if not k in now:
now[k] = {}
now = now[k]
now['value'] = value
def find(self, text, start=0):
now = self.d
n = len(text)
ret = None
pos = start
while pos < n:
if text[pos] in now:
now = now[text[pos]]
else:
return ret
if 'value' in now:
ret = (text[start:pos+1], now['value'])
pos += 1
return ret
def translate(self, text, with_not_found=True):
n = len(text)
pos = 0
ret = []
while pos < n:
now = self.d
if text[pos] in now:
tmp = self.find(text, pos)
if tmp:
ret.append(tmp[1])
pos += len(tmp[0])
continue
if with_not_found:
ret.append(text[pos])
pos += 1
return ret