解决问题:

  1. 对于每个提问,给出以该字符串为前缀的单词的数量
  2. 字符串匹配, 通过字典翻译 (map很容易爆炸)

小心RE!!! 别忘清空内存

  • 插入操作时，静态建树中插入不存在的结点利用的是已经创建好的大数组进行存放，而动态数组则会动态申请一个结点；
  • 删除操作时，静态建树中删除只需将跟节点的next数组都置为空即可，而动态建树中则要递归删除已经分配的每一个结点;
  • 动态建树使用new费时，静态建树预存结点数据很费空间；

1. 动态建树

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
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

struct Trie {
    int num;
    Trie* next[26];
    Trie() {
        for (int i = 0; i <= 25; i++) next[i] = NULL;
        num = 0;
    }
};

Trie *root = new Trie;

void Insert(char* word) {
    Trie* p = root;
    for (int i = 0; word[i]; i++) {
        if (p->next[word[i] - 'a'] == NULL) {
            p->next[word[i] - 'a'] = new Trie;
        }
        p = p->next[word[i] - 'a'];
        p->num++;
    }
}

void Freedom(Trie *p) {
    for (int i = 0; i < 26; i++) {
        if (p -> next[i] != NULL)
            Freedom(p -> next[i]);
    }
    delete p;
}

int Find(char* word) {
    Trie* p = root;
    for (int i = 0; word[i]; i++) {
        if (p->next[word[i] - 'a'] == NULL) {
            return 0;
        }
        p = p->next[word[i] - 'a'];
    }
    return p->num;
}

int main() {
    char word[11];
    int n, m;
    while (cin.getline(word, 12)) {
        if (strlen(word) == 0) {
            break;
        }
        Insert(word);
    }
    while (scanf("%s", word) != EOF) {
        printf("%d\n", Find(word));
    }
    Freedom(root);
    return 0;
}

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
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


#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;

int tree[maxn][30];
int flagg[maxn];

int tot;

void Insert(char *word) {
    int len = strlen(word);
    int root = 0;
    for (int i = 0; i < len; i++) {
        int id = word[i] - '0';
        if (!tree[root][id])
            tree[root][id] = ++tot;
        root = tree[root][id];
        flagg[root]++;
    }
    //flagg[root] += 1;
}

int Find(char* word) {
    int len = strlen(word);
    int root = 0;
    int ans = 0;
    for (int i = 0; i < len; i++) {
        int id = word[i] - '0';
        if (!tree[root][id])
            return 0;
        //if (flagg[tree[root][id]])
            //ans += 1;
        root = tree[root][id];
    }
    ans = flagg[root];
    return ans;
}

void init() {
    for (int i = 0; i <= tot; i++) {
        flagg[i] = false;
        for (int j = 0; j < 30; j++) {
            tree[i][j] = 0;
        }
    }
    tot = 0;
}

int main() {
    char word[11];
    int n, m;
    init();
    while (cin.getline(word, 12)) {
        if (strlen(word) == 0) {
            break;
        }
        Insert(word);
    }
    while (scanf("%s", word) != EOF) {
        printf("%d\n", Find(word));
    }
    return 0;
}

/*

banana
band
bee
absolute
acm

ba
b
band
abcf

*/