当前位置：首页 > article >正文

Trie（算法版）

article 2025/1/19 6:15:34

#include <iostream>

using namespace std;

const int N=100010;
int son[N][26],cnt[N],idx;
//son记录trie数，cnt记录每个词出现的次数，idx记录每个字符所占⽤的下标

//加入字符串
void add(char str[]){
	//idx = 0既表⽰根节点也表⽰空节点
	int p =0;
	for(int i =0;str[i];i++){  //字符串末尾为0
		int u = str[i]-'a';
		if(!son[p][u]){
			son[p][u]= ++idx;//当前字符不存在，增加
		}
		p=son[p][u];  //向下继续遍历
	}
	cnt[p]++;  //p指向字符串最后一个字符，计数++
}

int query(char str[]){
	int p =0;
	for(int i =0;str[i];i++){
		int u =str[i]-'a';
		if(!son[p][u]){
			return 0;//若没找到，直接返回0
		}
		p=son[p][u];
	}
	return cnt[p];  //p指向字符串的最后一个字符
}

int main(){
	int n;
	cin>>n;
	while(n--){
		char op;
		char x[N];
		cin>>op>>x;
		if(op=='I')add(x);
		else cout<<query(x)<<endl;
	}

	return 0;

}

假设情境 1096：我们有一个 Trie 树，开始时是空的。我们现在要插入以下两个单词：cat 和 car。

初始状态：

idx：初始值为 0，表示根节点。
son [N][26]：所有元素初始值为 0，表示 Trie 树是空的。

插入 “cat”：

字符 'c'：
- 计算索引 u = 'c' - 'a' = 2。
- 检查 son [0][2]，因为 Trie 树是空的，所以 son [0][2] 为 0。由于 son [0][2] 为 0，意味着当前节点 0 没有对应字符 'c' 的子节点。因此，我们创建一个新节点 1，并将 son [0][2] 设为 1，表示根节点 0 的 'c' 子节点是节点 1。
- 然后，将 p 更新为 1，即移动到节点 1。
- idx 增加到 1。
字符 'a'：
- 计算索引 u = 'a' - 'a' = 0。
- 检查 son [1][0]，此时 son [1][0] 仍为 0，因为之前还没有插入任何以 'a' 为第二个字符的单词。
- 因此，我们创建一个新节点 2，并将 son [1][0] 设为 2。
- 将 p 更新为 2，现在指向节点 2。
- idx 增加到 2。
字符 't'：
- 计算索引 u = 't' - 'a' = 19。
- 检查 son [2][19]，此时 son [2][19] 为 0，因为还没有插入任何以 't' 为第三个字符的单词。
- 创建新节点 3，并将 son [2][19] 设为 3。
- p 更新为 3，现在指向节点 3。
- idx 增加到 3。
- 此时，已成功插入 “cat”。p 当前指向节点 3，在 cnt [3] 上加 1，表示有一个单词以 't' 结尾。

再插入 “car”：

字符 'c'：
- 计算索引 u = 'c' - 'a' = 2。
- 检查 son [0][2]，此时 son [0][2] 为 1，表示根节点已经有一个 'c' 子节点，指向节点 1。
- 直接将 p 更新为 1，不用创建新节点。
字符 'a'：
- 计算索引 u = 'a' - 'a' = 0。
- 检查 son [1][0]，此时 son [1][0] 为 2，表示节点 1 有一个 'a' 子节点，指向节点 2。
- 将 p 更新为 2。
字符 'r'：
- 计算索引 u = 'r' - 'a' = 17。
- 检查 son [2][17]，此时 son [2][17] 为 0，因为还没有插入任何以 'r' 为第三个字符的单词。
- 创建新节点 4，并将 son [2][17] 设为 4。
- p 更新为 4。
- idx 增加到 4。
- 现在已成功插入 “car”。p 当前指向节点 4，在 cnt [4] 上加 1，表示有一个单词以 'r' 结尾。