题目描述

题目链接

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。
共有 N 个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

输入格式
第一行包含整数 N，表示操作数。

接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围
$1 ≤ N ≤ 2 ∗ 104$

输入样例：

1
2
3
4
5
6
5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
2
3
1
0
1

算法1

(数组模拟Trie树) $O(n)$

可以构造 Trie 前缀树来统计字符串集合中的字符

Trie树构造思路：

  • 每个单词从头开始， 依次将单词的每个字符插入到 Trie 树中，在插入过程中，将每个单词的 a - z 映射到 0 - 25
  • 可以使用 idx 来统计单词个数，第 0 个单词表示Trie 树的根，也表示单词的结尾
  • 在每个单词的结尾，使用 cnt 数组来统计在此处结尾的单词个数

空间复杂度： $O(26N)$

由于总共有 26 个单词，因此需要开辟 N * 26 维度的二位数组，这是本题空间的瓶颈

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
#include <iostream>

using namespace std;

const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
int n;

void insert(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if( !son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    
    cnt[p] ++; // 在 p 点结尾的单词数量加一
}

int query(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if( !son[p][u]) return 0;
        p = son[p][u];
    }
    
    return cnt[p];
}

int main()
{
    scanf("%d", &n);
    while( n --)
    {
        char op[2];
        scanf("%s%s", &op, &str);
        if( op[0] == 'I')
            insert(str);
        else
            printf("%d\n", query(str));
    }
    
    return 0;
}

算法1

(结构体构造Trie树) $O(n)$

使用数组模拟 Trie树 可以有效提高程序运行效率， 但是由于要开辟很多额外的空间，因此空间效率较低

为了优化空间效率，可以使用结构体来构造 Trie树

这种 Trie树 的构造思路更加接近 Trie树 的原理

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
#include <iostream>

using namespace std;
const int N = 100010;
char str[N];

struct Node {
    int cnt;
    Node* son[26];
    Node () {
        cnt = 0;
        for(int i = 0; i < 26; i ++)
            son[i] = NULL;
    }
} *root;

int n;

void insert(char str[])
{
    auto p = root;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if( !p->son[u]) p->son[u] = new Node();
        p = p->son[u];
    }
    
    p->cnt ++;
}

int query(char str[])
{
    auto p = root;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if( !p->son[u]) return 0;
        p = p->son[u];
    }
    return p->cnt;
}

int main()
{
    scanf("%d", &n);
    
    root = new Node();
    
    while (n -- )
    {
        char op[2];
        scanf("%s%s", &op, &str);
        if( op[0] == 'I')
            insert(str);
        else
            printf("%d\n", query(str));
    }
    
    
    return 0;
}