字典树 | StudyinCAU

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

题目描述

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

I x 向集合中插入一个字符串x；
Q x 询问字符串x在集合中出现了多少次。

共有n个操作，所有输入的字符串总长度不超过 $10^5$ ，字符串仅包含小写英文字母。

输入格式

第一行包含整数n，表示操作数。

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

输出格式

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

每个结果占一行。

数据范围

$1≤N≤2×10^4$

解答

#include<iostream>
using namespace std;

const int MAX_NODES = 1e6 + 10; // 最大节点数

int children[MAX_NODES][26], wordCount[MAX_NODES], nextIndex; // children数组存储节点的子节点, wordCount记录单词出现次数, nextIndex记录下一个可用的节点索引
char buffer[MAX_NODES];

// 向Trie树中插入一个字符串
void insertString(char str[]) {
    int node = 0; // 从根节点开始
    for (int i = 0; str[i]; i++) { // 遍历字符串的每个字符
        int charIndex = str[i] - 'a'; // 将字符转换为索引（0到25）
        if (!children[node][charIndex]) children[node][charIndex] = ++nextIndex; // 如果不存在这个字符的边，则创建一个新节点
        node = children[node][charIndex]; // 移动到下一个节点
    }
    wordCount[node]++; // 在字符串的最后一个字符对应的节点上增加计数
}

// 查询字符串在Trie树中出现的次数
int searchString(char str[]) {
    int node = 0; // 从根节点开始
    for (int i = 0; str[i]; i++) { // 遍历字符串的每个字符
        int charIndex = str[i] - 'a'; // 将字符转换为索引
        if (!children[node][charIndex]) return 0; // 如果这个字符在Trie树中不存在，则这个字符串不存在
        node = children[node][charIndex]; // 移动到下一个节点
    }
    return wordCount[node]; // 返回字符串最后一个字符对应的节点上的计数器的值
}

int main() {
    int operations; cin >> operations; // 操作的数量
    while (operations--) {
        char operationType[2];
        cin >> operationType >> buffer;
        if (operationType[0] == 'I') insertString(buffer); // 如果是插入操作，调用insertString函数
        else cout << searchString(buffer) << endl; // 如果是查询操作，调用searchString函数并输出结果
    }
    return 0;
}

但若是只是想要AC这道题的话，使用map可能会更简单。

代码如下

#include <iostream>
#include <map>
#include <string>
using namespace std;

map<string, int> counter; // 使用map来存储字符串及其出现次数

// 插入字符串，并增加其计数
void insert(const string& str) {
	counter[str]++;
}

// 查询字符串出现的次数
int search(const string& str) {
	if (counter.find(str) != counter.end())
		return counter.at(str);
	return 0;
}
int main() {
    int n;	cin >> n;
    StringCounter sc;
    while(n--) {
        string op, word;
        cin >> op >> word;
        if (op == "I") {
            sc.insert(word);
        } 
        else if (op == "Q") {
            cout << sc.search(word) << endl;
        }
    }
    return 0;
}