[模板]Trie树/字典树

Trie树利用字符串的公共前缀来降低查询时间的开销.

基于以空间换时间的思想,当有C个最大长度为N的字符串,字符串包含M种字符需要存储时,(均指本文中的实现,下同),最坏时间复杂度为O(N).

给定字符串最大长度和包含字符种数后,一个trie树就可以存储非常多的不同字符串:任何"定义域"内的字符串都可以各自存储到int的最大值数量个.

本文的实现使得空间复杂度达到最坏情况O(CNM),采取这种实现把trie的SIZE维设为N*C可以满足最坏情况的存储,即C个长度为N的字符串每个字符各自占据一个节点.

(关于trie树的空间复杂度:https://blog.csdn.net/dch19990825/article/details/104228662)

int trie[SIZE][26], tot = 1, ed[SIZE];      // SIZE = N * C, 假定字符串中只含小写字母

void insert(char *str) {
    int p = 1;
    for (int i = 0; str[i]; i++) {
        int ch = str[i] - 'a';
        if (!trie[p][ch]) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    ed[p]++;
}
int search(char *str) {　　　　// 返回字符串str出现次数,很多情况下只需要知道字符串是否出现了就可以了
    int p = 1;
    for (int i = 0; str[i]; i++) {
        p = trie[p][str[i] - 'a'];
        if (!p) return false;
    }
    return ed[p];
}

P2580是一道模板题,这里只需要使用trie树以记录字符串是否已经出现.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int trie[500010][26], tot = 1, ed[500010];
char s[60];

void insert(char *str) {
    int len = strlen(str), p = 1;
    for (int k = 0; k < len; k++) {
        int ch = str[k] - 'a';
        if (!trie[p][ch]) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    ed[p]++;
}

int search(char *str) {
    int len = strlen(str), p = 1;
    for (int k = 0; k < len; k++) {
        p = trie[p][str[k] - 'a'];
        if (!p) return 0;
    }
    return ed[p]++;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int n, m;
    scanf("%d", &n);
    while (n--) {
        scanf("%s", s);
        insert(s);
    }
    scanf("%d", &m);
    while (m--) {
        scanf("%s", s);
        int res = search(s);
        if(res == 1) puts("OK");
        else if(res == 0) puts("WRONG");
        else puts("REPEAT");
    }

    return 0;
}

P2922 [USACO08DEC]Secret Message G则需要记录字符串出现的次数.

题目中明确指出了位的总数不超过500000,即所有位最多占据5e5个节点(实际上根本不会发生),这就是trie树的SIZE了.

// 我实在懒得理解题解区一堆解法,就写了个很容易实现的记搜

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;
const int SIZE = 500010;

int s[10010];
int n, m;
int trie[SIZE][2], tot = 1, ed[SIZE];  // SIZE = N * C
int mem[SIZE];

void insert(int *str) {
    int p = 1;
    for (int i = 0; str[i] != -1; i++) {
        int ch = str[i];
        if (!trie[p][ch]) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    ed[p]++;
}
int dfs(int x) {
    if (mem[x] != -1) return mem[x];
    int ret = 0;
    int p1 = trie[x][0], p2 = trie[x][1];
    if (p1) ret += ed[p1] + dfs(p1);
    if (p2) ret += ed[p2] + dfs(p2);
    return mem[x] = ret;
}
int search(int *str) {
    int p = 1, ret = 0;
    for (int i = 0; str[i] != -1; i++) {
        p = trie[p][str[i]];
        ret += ed[p];
    }
    return ret + dfs(p);
}

int main() {
    memset(mem, -1, sizeof(mem));
    scanf("%d%d", &m, &n);
    while (m--) {
        int b;
        scanf("%d", &b);
        for (int i = 0; i < b; i++) cin >> s[i];
        s[b] = -1;
        insert(s);
    }

    while (n--) {
        int c;
        scanf("%d", &c);
        for (int i = 0; i < c; i++) cin >> s[i];
        s[c] = -1;
        printf("%d
", search(s));
    }
    // printf("Time used = %.3fs.
", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}