博客

字典树的递归感觉和kmp的next数组有点像。

就我而言，字典树难理解不是对树的疑问，而是对数组里面该填什么数字感到疑惑（我很菜，想了好久才迷糊过来）。

例如：

3
abc
abd
bcd

U数组（i从0开始）

输入abc时

第一行 1 0 0 0 …

第二行 0 2 0 0 …

第三行 0 0 3 0…

输入abd时

第一行 1 0 0 0…

第二行 0 2 0 0…

第三行 0 0 3 4…

输入bcd时

第一行 1 0 0 5…

第二行 0 2 0 0

第三行0 0 3 4

第四行 0 0 0 0

第五行 0 0 0 0

第六行 0 0 6 0

第七行 0 0 0 7

自己手磨时每一行加上 i 的值

可能会好理解

	int n;int idx=1;
	cin>>n;
	while(n--)
	{
		int j=0;
		cin>>C+1;
		int len=strlen(C+1);
		for(int i=1;i<=len;i++)
		{
			int x=C[i]-'a'+1;
			if(U[j][x]==0)
			{
				U[j][x]=idx;
				idx++;
			}
			j=U[j][x];
		}
		V[j]=1;//如果是单词，加上单词结尾的判断
	}