问题背景

在字符串处理中，经常需要高效地完成以下任务：

• 判断一个字符串是否在字典中出现过
• 处理重复查询（如点名系统中的重复呼叫）
• 检查是否存在某个字符串是另一个字符串的前缀

下面通过两个具体问题讲解Trie树的实现方法。

问题一：点名系统（P2580）

给定一个学生名单，老师逐个点名，需要判断每个名字的状态：第一次被点到输出"OK"，重复被点到输出"REPEAT"，不存在于名单中输出"WRONG"。利用Trie树存储名字并记录访问次数

C++实现

#include <bits/stdc++.h>
using namespace std;

const int MAX_NODES = 5e5 + 5;
int node_count = 0;

struct TrieNode {
    int child[27];
    bool is_end;
    int visit_count;
} trie[MAX_NODES];

void add_string(const string& s) {
    int cur = 0;
    for (char ch : s) {
        int idx = ch - 'a';
        if (!trie[cur].child[idx])
            trie[cur].child[idx] = ++node_count;
        cur = trie[cur].child[idx];
    }
    trie[cur].is_end = true;
}

int query_string(const string& s) {
    int cur = 0;
    for (char ch : s) {
        int idx = ch - 'a';
        if (!trie[cur].child[idx])
            return 3; // 不存在
        cur = trie[cur].child[idx];
    }
    if (!trie[cur].is_end)
        return 3; // 不完整匹配
    if (trie[cur].visit_count == 0) {
        trie[cur].visit_count++;
        return 1; // 首次出现
    }
    return 2; // 重复出现
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    string name;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> name;
        add_string(name);
    }
    
    cin >> m;
    while (m--) {
        cin >> name;
        int result = query_string(name);
        if (result == 1) cout << "OK\n";
        else if (result == 2) cout << "REPEAT\n";
        else cout << "WRONG\n";
    }
    
    return 0;
}

问题二：前缀判断（UVA11362 Phone List）

给定一组电话号码，判断是否存在一个号码是另一个号码的前缀。例如，"911"是"91125426"的前缀。这里需要在Trie中记录每个节点经过的字符串数量。

C++实现

#include <bits/stdc++.h>
using namespace std;

const int MAX_NODES = 4e5 + 5;

struct TrieNode {
    int child[11];
    int prefix_count;
    bool is_end;
    
    void reset() {
        memset(child, 0, sizeof(child));
        prefix_count = 0;
        is_end = false;
    }
} trie[MAX_NODES];

int total_nodes = 0;

void clear_all() {
    for (int i = 0; i < MAX_NODES; i++)
        trie[i].reset();
    total_nodes = 0;
}

void insert_number(const string& s) {
    int cur = 0;
    for (char ch : s) {
        int idx = ch - '0';
        if (!trie[cur].child[idx])
            trie[cur].child[idx] = ++total_nodes;
        trie[cur].prefix_count++;
        cur = trie[cur].child[idx];
    }
    trie[cur].is_end = true;
}

bool check_prefix(const string& s) {
    int cur = 0;
    for (char ch : s) {
        int idx = ch - '0';
        if (!trie[cur].child[idx])
            return false;
        cur = trie[cur].child[idx];
    }
    return trie[cur].prefix_count > 0;
}

int main() {
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        clear_all();
        
        int n;
        cin >> n;
        vector<string> numbers(n);
        
        for (int i = 0; i < n; i++) {
            cin >> numbers[i];
            insert_number(numbers[i]);
        }
        
        bool has_prefix = false;
        for (const string& s : numbers) {
            if (check_prefix(s)) {
                has_prefix = true;
                break;
            }
        }
        
        cout << (has_prefix ? "NO\n" : "YES\n");
    }
    
    return 0;
}

核心思想

• 插入操作：从根节点开始，根据字符逐步向下创建或遍历子节点，并在结尾标记。
• 查询操作：沿路径查找，检查是否存在完整匹配或前缀，同时可记录访问次数。
• 前缀检测：在插入时累计经过的节点次数，查询时通过判断某个节点是否有子节点或计数来确认前缀关系。

Trie树能以O(L)时间复杂度处理字符串（L为字符串长度），适用于大量字符串查找、前缀匹配等场景。