字符串学习笔记二

• 2020 年 7 月 24 日
• 笔记
• 字符串--字典树, 集训总结

配合上一篇效果更佳—>字符串学习笔记一

4.0 四、字典树

定义

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

实现

从百度百科瞟的图

字典树一般用一个二维数组定义，\(tr[now][t]\)表示\(now\)节点的字符为\(t\)的儿子的编号
同时我们还要开一个数组\(cnt[now][t]\)表示该节点的个数
在某些情况下，我们还要记录有几个字符串在该节点终结、该节点属于第几个字符串等等
一般来说，字典树支持两种操作：插入和查询
假如要插入某个单词
一开始我们位于根节点，也就是\(0\)号节点
接下来我们判断根节点是否有某一个儿子\(ch\)
即\(tr[now][ch]\)是否等于\(0\)
如果等于\(0\)，那我们再新开一个节点，否则把该节点的个数加一
查询操作也是如此，我们就从根节点一路走下去
如果可以走完，说明该单词存在，否则该单词不存在

代码实现

以洛谷P2922为例

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e7+5;
char c[maxn];
int tr[maxn][3],cnt[maxn][3],tot,ed[maxn][3];
void ad(char s[]){
    int len=strlen(s);
    int now=0;
    for(int i=0;i<len;i++){
        int t=s[i]-'0';
        if(tr[now][t]){
            cnt[now][t]++;
        } else {
            tr[now][t]=++tot;
            cnt[now][t]=1;
        }
        if(i==len-1) ed[now][t]++;
        now=tr[now][t];
    }
}
int cx(char s[]){
    int len=strlen(s);
    int now=0,ans=0,js=0,jud=0,t;
    for(int i=0;i<len;i++){
        t=s[i]-'0';
        if(tr[now][t]){
            js+=ed[now][t];
            if(i!=len-1)now=tr[now][t];
        } else {
            jud=1;
            break;
        }
    }
    if(jud) return js;
    else return js-ed[now][t]+cnt[now][t];
}
char s[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        int aa;
        for(int j=1;j<=t;j++){
            scanf("%d",&aa);
            s[j-1]=aa+'0';
        }
        s[t]='\0';
        ad(s);
    }
    for(int i=1;i<=m;i++){
        int t;
        scanf("%d",&t);
        int aa;
        for(int j=1;j<=t;j++){
            scanf("%d",&aa);
            s[j-1]=aa+'0';
        }
        s[t]='\0';
        printf("%d\n",cx(s));
    }
    return 0;
}