字典树

发表于 更新于

一、常用模板

1、用邻接矩阵表示(耗费内存，速度快)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int maxn = 400005;
int pos = 0;
int trie[maxn][26];
bool trieExists[maxn];
void insert(char *s){
    int p = 0;
    while(*s) {
        int c = *s++ - 'a';
        if(!trie[p][c]) trie[p][c] = ++pos;
        p = trie[p][c];
    }
    trieExists[p] = 1;
}
int find(char *s){
    int p = 0;
    while(*s){
        int c = *s++ - 'a';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return trieExists[p];
}

2、用邻接表表示(节约内存，数据分散时遍历快)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int tHeads[maxn];
int tNode[maxn]; int ncnt = 0;
int tNodeVal[maxn];

int trieExistsCount[maxn];
int trieJoinCount[maxn];
void insert(char *s) {
    int p = 0;
    while (*s) {
        ++trieJoinCount[p];
        int c = *s++;
        int nex = tHeads[p];
        while(nex && tNodeVal[nex] != c) nex = tNode[nex];
        if (!nex) {
            int bf = tHeads[p];
            tHeads[p] = ++ncnt;
            tNode[ncnt] = bf;
            tNodeVal[ncnt]  = c;
            p = ncnt;
        }
        else p = nex;
    }
    ++trieExistsCount[p];
    ++trieJoinCount[p];
}

二、相关习题

1、UVA1401

直接套用模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
const int maxn = 400005;
int pos = 0;
int trie[maxn][26];
bool trieExists[maxn];
void insert(char *s){
    int p = 0;
    while(*s) {
        int c = *s++ - 'a';
        if(!trie[p][c]) trie[p][c] = ++pos;
        p = trie[p][c];
    }
    trieExists[p] = 1;
}
int find(char *s){
    int p = 0;
    while(*s){
        int c = *s++ - 'a';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return trieExists[p];
}

char W[300005];
char S[105];
int DP[300005];
int main()
{
    int kase = 0;
    while(~scanf("%s",W)){
        memset(DP,0,sizeof(DP));
        memset(trie,0,sizeof(trie));
        memset(trieExists,0,sizeof(trieExists));
        int n = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; ++i) scanf("%s", S), insert(S);
        int wl = strlen(W);DP[0]=1;
        for(int i = 0; i < wl; ++i){
            int j = i, p = 0,c;
            while(j < wl){
                c = W[j] - 'a';
                p = trie[p][c];
                if(!p) break;
                if(trieExists[p]) DP[j+1] = (DP[j+1] + DP[i])%20071027;
                ++j;
            }
        }
        //for(int i = 0; i <= wl; ++i) printf("%d ", DP[i]);puts("");
        printf("Case %d: %d\n",++kase, DP[wl]);
    }
    return 0;
}

2、⭐UVA11732

用邻接矩阵会TLE，需要用邻接表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#define _CRT_SECURE_NO_WARNINGS
#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
const int maxn = 4002205;


int tHeads[maxn];
int tNode[maxn]; int ncnt = 0;
int tNodeVal[maxn];

int trieExistsCount[maxn];
int trieJoinCount[maxn];
int codeMap[] = {-61,-60,-59,-58,-57,-56,-55,-54,-53,-52,-51,-50,-49,-48,-47,-46,-45,-44,-43,-42,-41,-40,-39,-38,-37,-36,-35,-34,-33,-32,-31,-30,-29,-28,-27,-26,-25,-24,-23,-22,-21,-20,-19,-18,-17,-16,-15,-14,0,1,2,3,4,5,6,7,8,9,-3,-2,-1,0,1,2,3,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,-189,-188,-187};
void insert() {
    int p = 0;
    while (1) {
        char ch = getchar();
        if (ch == '\n') break;
        ++trieJoinCount[p];
        int c = codeMap[ch];
        
        int nex = tHeads[p];
        while(nex && tNodeVal[nex] != c) nex = tNode[nex];
        if (!nex) {
            int bf = tHeads[p];
            tHeads[p] = ++ncnt;
            tNode[ncnt] = bf;
            tNodeVal[ncnt]  = c;
            p = ncnt;
        }
        else p = nex;
    }
    ++trieExistsCount[p];
    ++trieJoinCount[p];
}
long long int ans = 0;
long long int dc = 0;
void dfs(int p,int last) {
    int f = trieExistsCount[p];
    int j = trieJoinCount[p];
    if (j && last) {
        // 计算与兄弟节点的比较次数，这里会计算两次
        dc += (last - j) * j;
        //cout << "dc" << (last - j) * j << endl;
        // 计算当前节点相等值比较次数，a,a,a,ac,ac,ac 需要计算5*4次
        ans += j * (j - 1);
        //cout << "self:" << j * (j - 1) << endl;
        // 计算当前节点的终止节点与非终止比较次数，a,a,a,ac,ac,ac 需要计算3*3次
        ans += f * (j - f);
        //cout << "diff:" << f * (j - f) << endl;
        // 计算当前节点的终止节点比较次数，a,a,a,ac,ac,ac 需要计算3*2/2*2次
        ans += f * (f - 1);
        //cout << "end:" << f * (f - 1)  << endl;
    }
    int t = j - f;
    int nex = tHeads[p];
    while(nex){
        dfs(nex, t);
        nex = tNode[nex];
    }
}
char S[1005];
int main()
{
    //freopen("1.txt", "r", stdin);
    int kase = 0; int n;
    while (~scanf("%d", &n) && n) {
        ans = 0, dc = 0, ncnt = 0;
        memset(trieExistsCount, 0, sizeof(trieExistsCount));
        memset(trieJoinCount, 0, sizeof(trieJoinCount));
        memset(tHeads, 0, sizeof(tHeads));
        getchar();
        for (int i = 0; i < n; ++i) {
            insert();
        }
        dfs(0, 0);

        //for(int i = 0; i <= wl; ++i) printf("%d ", DP[i]);puts("");
        printf("Case %d: %lld\n", ++kase, ans + dc/2);

    }
    return 0;
}