字符串-Trie字典树

Skyzhou666 · 2024-09-10 16:09:41 · 算法·理论

Trie

增查模板

#include <iostream>
#define MAXN 1001
using namespace std;

int son[MAXN][26], cnt[MAXN], idx;

void insert(string s)
{
    int p = 0; //指向当前节点
    for(int x = 0; x < s.length(); x++)
    {
        int u = s[x] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(string s)
{
    int p = 0;
    for(int x = 0; x < s.length(); x++)
    {
        int u = s[x] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n, m;
    string s;
    cin >> n >> m;
    for(int x = 0; x < n; x++)
    {
        cin >> s;
        insert(s);
    }
    for(int x = 0; x < m; x++)
    {
        cin >> s;
        cout << query(s) << endl;
    }
    return 0;
}

这篇kingwzun的blog讲的不错

P2922 USACO Secret Message G

基本上就是模板，但考虑到题目询问的是有关前缀的问题，要稍微小改一下

#include <iostream>
#include <cstring>
#define MAXN 500001
using namespace std;

int inp[MAXN], son[MAXN][2], cnt[MAXN], idx, wrd[MAXN];

void trie_insert(int i)
{
    int p = 0;
    for(int x = 0; x < i; x++)
    {
        int u = inp[x];
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
        cnt[p]++;
    }
    wrd[p]++;
}

int trie_query(int i)
{
    int p = 0, ans = 0;
    for(int x = 0; x < i; x++)
    {
        int u = inp[x];
        if(!son[p][u]) return ans;
        p = son[p][u];
        ans += wrd[p];
    }
    return ans-wrd[p]+cnt[p];
}

int main()
{
    int n, m, i;
    cin >> m >> n;
    while(m--)
    {
        cin >> i;
        for(int x = 0; x < i; x++) cin >> inp[x];
        trie_insert(i);
    }
    while(n--)
    {
        cin >> i;
        for(int x = 0; x < i; x++) cin >> inp[x];
        cout << trie_query(i) << endl;
    }
    return 0;
}