class Trie:
root={}
END='/'
def add_province(self,word):
node=self.root
for c in word:
if c=='省':
node[self.END]='省'
elif c=='自':
node[self.END]='自治区'
break
else:
node=node.setdefault(c,{})
def find_province(self,word):
node=self.root
#flag为前置flag,bflag为后置flag
fflag=0
bflag=0
province=[]
for c in word:
#假设flag不为0，代表找到省份的第一个关键字。假设此时节点包含结束字符，则定义bflag=1,读取下一个字符
if fflag!=0 and self.END in node:
#定义后向查找标识，排除陕西南路之类的情况
if re.search('路|街|岸|道|苑|侧|镇|园|区|第|村|坡|乡|项|里',c) is not None:
province=[]
fflag=0
node=self.root
continue
else bflag<2:
bflag=bflag+1
continue
else return ''.join(province)
#假设bflag==1，表明已经找到一次省份。第一次后后续匹配找到省份名称，设flag=1,存储省份名称，继续后一级查找
elif c in node:
fflag=1
province.append(c)
node=node[c]
#在地址中逐字查找是否有省份的第一个关键字，直到找到,flag标为1，否则0
elif c not in node:
if fflag==0:
continue
#假如第一次找的不匹配，但该关键字在根节点属于省份的第一个字符，则清空已经找到的省名，把第一个字符读入省名，flag置为1，并读入第二个省名字符。否则，flag重新标为0，返回根节点查找省名。
elif c in self.root:
province=[]
fflag=1
province.append(c)
node=self.root[c]
continue
else:
province=[]
fflag=0
node=self.root
continue
#假如遍历完毕，找到第一个省份字符且当前字符为地址的最后一个字符（地址中只有省份名称也没出现“省”字的特殊情况）
if fflag!=0 and self.END in node:
return ''.join(province)
return False
