字典树Trie

概念

• 字典，即字符串的集合；
• 字典树，英文名 Trie，顾名思义，是一个像字典一样的树。
• 基础应用：查找一个字符是否在【字典】中出现过。

插入

int next[100001][26],cnt;
bool exist[1000001];//该节点结尾的字符是否存在

void insert(char *s,int l)
{
	int p = 0;
	for(int i = 0;i < l;i++)
	{
		int c = s[i] - 'a';
		if(!next[p][c]) next[p][c] = ++cnt;
		p = next[p][c];
	}
	exist[p] = true;
	return;
}

查找

bool find(char *s,int l)
{
	int p = 0;
	for(int i = 0;i < l;i++)
	{
		int c = s[i] - 'a';
		if(!next[p][c]) return false;
		p = next[p][c];
	}
	return exist[p];
}