trie（字典树）

发表于 | 分类于 |

什么是$trie$(字典树)

$trie$是一棵保存多个字符串的树。

如图：

trie

这棵字典树就保存着$8$条字符串：{to,tea,ted,a,i,in,inn}。

从根节点到某特定节点的路径就是对应的字符串。如上图节点编号为红色的点就说明：从根节点到该节点的路径为一个保存了的字符串。

具体实现

用$trie[i][j]$表示节点$i$走$j$字母到达的点的编号（根的编号为0），如上图：

$trie[0][t]=1,trie[1][o]=2,trie[1][e]=3,trie[3][a]=4,…,trie[9][n]=10$。

字母一般用编号$0$到$m$代替，有时可能还会有大写字母，数字之类的。

然后用一个$val$数组保存以该点为结尾的字符串的个数，如上图：$val[0]=0,val[1]=0,val[2]=1,val[3]=0,…,val[10]=1$。

有时候可能会有多个相同字符串，所以$val$数组保存的数可能大于零。

建$trie$程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void buildtrie(int x)
{
	int u=0,m=strlen(str[x]);
	for(int i=0;i<m;i++)
	{
		int v=T(str[x][i]);
		if(trie[u][v]==0)                          //开新节点
		{
			trie[u][v]=++se;
			val[se]=0;
			memset(trie[se],0,sizeof(trie[se]));
		}
		u=trie[u][v];                              //接着往下走
	}
	val[u]++;
}
int main()
{
	scanf("%d",n);
	for(int i=0;i<n;i++)
	{
		scanf("%s",str[i]);
		buildtrie(i);
	}
	return 0;
}

例题：UVALive3942（题解戳这)）