字典树详解

字典树

英文名 Trie

字典树又称前缀树；

如图:

其特点:
1.根结点为空；
2.除根结点以外，每个结点都可以储存一个单词；
3.每个非叶子结点一般会用到多次；
4.一般是叶子结点存储附加信息；

一般操作为插入和查询；切记数组开大一点

模板：

int tree[N][30],rt,val[N];
void add(string s,int p){//s为要插入的字符串，p为附加信息
	int k=0;//根结点
	int len=s.length();
	for(int i=0;i<len;i++){
		int d=s[i]-'a';
		if(!tree[k][d]){
			val[k]=0;//中间结点没有信息
			tree[k][d]=++rt; 
		}
		k=tree[k][d];//继续往下遍历 
	}
	val[k]=p;//一般只有叶子结点才有信息 
}
int search(string s){
	int k=0;
	int len=s.length();
	for(int i=0;i<len;i++){
		int d=s[i]-'a';
		if(!tree[k][d]) return -1;
		k=tree[k][d];
	}
	return val[k];
}