835. Trie字符串统计

本文主要是介绍835. Trie字符串统计，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这个问题在于理解son这个数组，首先字典树可以理解为一层一层的，
首先，为什么是son[N][26]最长长度的字符串有N个字母，每个字母有26种可能所以就是这样。(其实一共字符串比如abc，可以算三种情况， a, ab, abc。）
比如这个：

son[0]就理解为第一层，也就是字符串第一个字符，对应字符串的第一个字母的26个可能的字母，所以有26个位置,字符串第二个字母就是son[1],也有26种可能，
而son[0][0],假如第一个加入的字符串abc第一个字母为a这个son[0][0]这一项就等于1，然后son[1][1]等于2，son[2][2]等于3，(这里的 1 2 3 就是idx（idx就是第几种情况))
（100000个字符串所以有100000种情况，son[][]对应的值就是每一项对应结尾的序号，此时cnt[son[][]]++）
第二个字符串abd就 a和b都已经出现过了所以一直到
第三个字母son[2][3]等于4，表示此前的字符串都不符合当前这个情况，出现的第四种情况。

#include<bits/stdc++.h> 
using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
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];  //使“p指针”指向下一个节点位置
    }
    cnt[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;
        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));
    }
}

这篇关于835. Trie字符串统计的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！