【算法】Tire字符串

作者：指针不指南吗
专栏：算法篇

🐾或许会很慢，但是不可以停下🐾

1.Trie的基本思想

1.1什么是Trie

Trie是用来快速高效查找和查找字符串集合的数据结构。

1.2字符串条件

字符串需要 全是大写，全是小写，0或者1，数字

为什么不能是汉字呢?

因为我们需要把字符串的每个字符映射到每个数组里面去存储，比如全是小写英文的我们需要数组大小为26，那如果是汉字的话，要开个几万的数组，有点麻烦困难，所以字符串都是上述几种情况。

1.3如何存储字符串

具体过程如下（图是借用acwing佬的）

用树来存储字符串；

根节点为0，这里省略根节点；

比如存储字符串abcd ：

• 从第一个节点开始，如果第一个节点是a,就往下走，否则就创建一个 a ，
• 然后是第二个字符b，找第一个节点的son 如果，son是b,就继续找下找，否则就创建一个
• 依次往下直到最后一个字符d,最后在字符结束的地方，标记一下

1.4如何查找字符串

同样利用上图,而且和存储操作很相似

比如查找字符串abcd :

• 从第一个节点开始,如果是 a ,就通过它的son找下一个字符b,没有a 字符,返回0;
• 找第二个字符b,通过第一个节点的son 查找,如果是,找下一个,没有返回0;
• 直到找到最后一个,如果能找到最后一个,并且最后一个上面有字符串结束的标志,返回字符串的个数;

2.Trie的代码实现

先放例题,便于理解

Trie字符串统计

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

1. I x 向集合中插入一个字符串 x；
2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，所有输入的字符串总长度不超过 105105，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N，表示操作数。

接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤$2\ast 10^4$

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

2.1怎么用数组建树

这里比较难懂重点, 我们用一个二维数组去建树 son[N][26]

一维是现在位置是第几个结点(下标)，二维是结点和结点之间的关系（谁是谁儿子）;

比如son[0][1]=3, [0]表示根节点，[1]表示它有一个儿子b,这个儿子的下标是3；

接着如果有son[3][4]=8 ; 说明根节点的儿子b也有一个儿子c，这个孙子的下标就是8；

这样传递下去，就是一个字符串。

随便给一个结点son[x][y] 并不能看出它在第几层，只能知道，它的儿子是谁。

2.2完整代码

#include<iostream>
using namespace std;const int N=200010;
int son[N][26],idx,cnt[N];
char str[N];void insert(char *str)
{int p=0;  //从根节点开始，找字符for(int i=0;str[i];i++)  //字符串是以'\0'结尾的，可以当作是判断条件{int u=str[i]-'a';  //把26个英文字母映射到 数字 0~25，便于数组存储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;  //没有想要的节点，说明字符不存在，返回0p=son[p][u];  //下一个节点，继续查找下一个字符}return cnt[p];  //可以按着这个路径走下来，说明有这个字符串，返回字符串的数量
}int main()
{int n;cin>>n;while(n--){char op[2];scanf("%s%s",op,str);if(*op=='I') insert(str);else printf("%d\n",query(str));}return 0;
}