Tire(字典树)

• Tire是一种用于实现字符串快速检索的多叉树结构。Trie的每个结点都拥有若干个字符指针，若在插入或者检索字符串时扫描到一个字符c，就沿着当前结点的c字符指针走向该指针指向的节点。
• 初始化：

一颗空Trie仅包含一个跟节点，该点的字符指针均为空

• 插入

当需要一个字符串S时，我们令一个指针p起初指向根节点。然后，依次扫描S中的每个字符c：

1：若p的c字符指针指向空，则新建一个节点Q，令P的c字符指针指向Q，然后P=Q；

2：若p的c字符指针指向一个已经存在的节点Q，则令P=Q；

当S中的字符扫描完毕时，在当前节点p上标记它是一个字符串的末尾。

• 检索

当需要检索一个字符串S在Trie中是否存在时，我们令一个指针p起初指向根节点，然后依次扫描S中的每个字符c：

1：若p的c字符指针指向空，则说明S中没有被插入过Trie，结束检索。

2：若p的c字符指针指向一个已经存在的节点Q，则令P=Q。

当S中的字符扫描完毕时，若当前节点P被标记为一个字符串的末尾，则说明在Trie中存在，否则说明S没有被插入过Trie。

• 实际上，可以看作一个链表的检索，其空间复杂度为O(NC);

const int MAXN = 1e6+10; 
int trew[maxn][26],tot=1;
bool end[maxn];
char s[maxn];
void insert(char *str){
	int len = strlen(str), p=1;
	for(int k=0;k<len;k++){
		int ch=str[k]-'a';
		if(trie[p][ch]==0)trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	end[p]=true;
}
bool search(char *str){
	int len=strlen(str),p=1;
	for(int i=0;i<len;i++){
		int ch=str[i]-'a';
		if(trie[p][ch]==0)return false;
		p=trie[p][ch];
	}
	return end[p];
}