Trie字符串统计数组实现

字典树 (Trie)

字典树，英文名 trie。顾名思义，就是一个像字典一样的树。

基本性质：

1.根节点不包含字符，除根节点外的每一个子节点都包含一个字符

2.从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串

3.每个节点的所有子节点包含的字符都不相同

用数组来存取树方法实现：

首先准备一个二维数组

son[N][M]

和一个结点编号器

idx

。

思想：

1.

son

中的

N

表示父结点的编号，

M

表示该点字符元素，整个

son[N][M]

表示父结点为

N

，字符元素为

M

的结点（实际就是通过父节点来访问孩子结点）。

2

idx

的作用是给结点编号，使每一个结点独一无二(实际为了给父节点命个名来区分父节点)。

例：

输入三个字符串形成的树。

a b c

a b

b d

代码实现：

void insert()
{
	int p = 0; //根节点
	for (int i = 0; c[i]; i++)
	{
		int u = c[i] - 'a'; // 孩子结点对应的元素,字符不能当下标
 		if (!son[p][u]) son[p][u] = ++idx; // 给孩子结点编号，实际是为了区分结点
		p = son[p][u]; // 孩子结点做父结点
	}
}
           

图像：

每个结点前面的数代表结点编号。

通过结点编号（父结点）可以访问，该结点的孩子结点，即

son[N][M]

中的

N

。

但只知道结点编号还不行，还需要知道孩子元素，来确定访问哪个孩子结点。

例：编号为

1

的结点的孩子对应的孩子元素为

b

，

d

，即孩子元素为

b

对应的结点为

son[i][b]

（这里不能真的用b）该结点的值为该结点的编号。

例题：

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 x；

Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，字符串仅包含小写英文字母。

实现代码：

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

char c[N];
int son[N][26]; // 孩子结点
int cnt[N]; // 统计字符串
int idx; // 结点编号器


void insert()
{
	int p = 0;
	for (int i = 0; c[i]; i++)
	{
		int u = c[i] - 'a'; // 孩子结点对应的元素
 		if (!son[p][u]) son[p][u] = ++idx; // 给孩子结点编号，使孩子节点独一无二
		p = son[p][u]; // 孩子结点做根结点
	}
	// 从根节点到此孩子结点的字符串出现的次数，
	// 因为每个子树都是独一无二的，因此p对应的子树也是独一无二的
	// 所以只要保证叶子结点加1，就可以表示这个子树加1。
	cnt[p]++; 
}

void query()
{
	int p = 0;
	for (int i = 0; c[i]; i++)
	{
		int u = c[i] - 'a';
		p = son[p][u];
	}
	cout << cnt[p] << endl;
}

int main()
{
	int n; cin >> n;
	while (n--)
	{
		char op[2];
		scanf("%s%s",op, c);
		if (op[0] == 'I') insert();
		else query();
	}
}