【Tire树】高效统计字符串

2023-02-25 17:57:15 来源：博客园

【资料图】

导读 ^ _ ^

Tire树是很关键的一种数据结构，你应该听过他的另外一个名字，即字典树，可以高效存储和查找字符串集合。

何为Tire树

一种高效存储和查找字符串集合的数据结构结尾进行标记，统计出现次数

字符串统计

表示方式

son数组

第一维度用了表示节点，由idx控制
第二维度用来表示当前子节点枝条，有26个字母构成

cnt数组

用来统计当前节点出现的次数

关系映射

将字符 - ‘a’映射成数字

#include#includeusing namespace std;const int N = 100010;int son[N][26], cnt[N], idx;//注意0是根节点，又是空节点char str[N];void insert(char str[ ]) {    int p = 0;    for (int i = 0; str[i]; i++) {       int u = str[i] - "a";       if(!son[p][u]) son[p][u] = ++idx;//当前没有用过       p = son[p][u];//用过了，下个儿子    }    cnt[p]++;//最终儿子结尾+1}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;//结尾没有继续了        p = son[p][u];//下一个儿子    }    return cnt[p];}int main( ) {    int n;    scanf("%d", &n);    while(n--) {        char op[2];//过掉一个换行        scanf("%s%s",op,str);        if(op[0] == "I")insert(str);        else printf("%d\n",query(str));    }    return 0;}

#谢谢你的观看！

^ _ ^

关键词：数据结构另外一个