字典树板子

2023/3/2 Trie 字符串

做道板子

我们考虑将一组字符串转化为树的形式

我们使得每个结点之间连接的边表示一个字符，那么对于一个结点，它可以连接有限个结点（假设字符只有a-z，那么一个结点最多连接26个亲儿子），

于是我们以图示为例子，以“cd”结尾的字符串有两个，分别为 “cdf” 和 “cdh”，所以我们可以在初始化的时候更新trie数组，

我们用trie[p][x] 数组表示p结点连接的字符x是否存在，那么我们可以用Ascall来替代字符的数字，因为本题的字符有数字有字母，所以我们以ascall值最小的0来做基底

以cnt来表示结点编号

void in(string s){
    int p = 0, n = s.size();
    rep(i, 0, n - 1){
        int x = s[i] - '0';
        if(!trie[p][x]) trie[p][x] = ++ cnt; // 如果该节点没有连接s[i]，那么新增结点编号
        p = trie[p][x]; // 下传结点
        ans[p] ++; //以该结点结尾的字符串个数
    }
}

于是我们便可以便捷地查询有s前缀字符串的个数

int get(string s){
    int p = 0, n = s.size();
    rep(i, 0, n - 1){
        int x = s[i] - '0';
        if(!trie[p][x]) return 0; //还没找完就没有了，直接 return 0
        p = trie[p][x];
    }
    return ans[p]; //
}

注意trie数组的大小，因为本题一次性预处理的字符串个数有 1e5，所以在累加结点编号的时候难免会超出很多

#include <bits/stdc++.h>
#define rep(i, n, m) for(int i = n; i <= m; ++i)
using namespace std;
const int N = 3e6 + 10;
int ans[N], trie[N][150], cnt;
void in(string s){
    int p = 0, n = s.size();
    rep(i, 0, n - 1){
        int x = s[i] - '0';
        if(!trie[p][x]) trie[p][x] = ++ cnt;
        p = trie[p][x];
        ans[p] ++;
    }
}
int get(string s){
    int p = 0, n = s.size();
    rep(i, 0, n - 1){
        int x = s[i] - '0';
        if(!trie[p][x]) return 0;
        p = trie[p][x];
    }
    return ans[p];
}
void solve()
{
    // 初始化
    rep(i, 0, cnt){
        ans[i] = 0;
        rep(j, 0, 140) trie[i][j] = 0;
    } cnt = 0;

    int n, q; cin >> n >> q;
    rep(i, 1, n){
        string s; cin >> s;
        in(s);
    }
    rep(i, 1, q){
        string s; cin >> s;
        cout << get(s) << '\n';
    }
}
int main()
{
    //ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    while(n--) solve();
    return 0;
}

延申题下次再更新。。。。

LOADING

字典树板子