数据结构核心：KMP 算法、Trie 树与并查集详解

下面是一个完整的模板，注意这里习惯用 1-based 索引，方便理解逻辑。

#include<iostream>
using namespace std;
const int N = 1e4 + 10;
const int M = 1e5 + 10;
char S[M], P[N], ne[N];
int n, m;

int main(){
    cin >> n >> (P + 1) >> m >> (S + 1);
    
    // 1. 预处理 next 数组
    for(int i = 2, j = 0; i <= n; i++){
        while(j && P[i] != P[j + 1]) j = ne[j];
        if(P[i] == P[j + 1]) j++;
        ne[i] = j;
    }
    
    // 2. 匹配过程
    for(int i = 1, j = 0; i <= m; i++){
        while(j && S[i] != P[j + 1]) j = ne[j];
        if(S[i] == P[j + 1]) j++;
        if(j == n){
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}

Trie 树

Trie 树（字典树）是一种专门用来快速存储和查找字符串集合的数据结构。它的核心思想是利用字符串的公共前缀来减少查询时间。

想象一下，我们要存一堆单词。从根节点出发，每个单词的字母对应一条路径。为了标记某个单词是否结束，我们在节点上记录一个计数值 cnt。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
char str[N];
int son[N][26], cnt[N], idx; // son[p][u] 表示 p 节点的 u 号儿子下标

// 插入操作
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]++; // 标记该单词出现次数
}

// 查询操作
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(){
    int n;
    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. 判断树根：如果 p[x] == x，说明 x 是根。
2. 查找集合编号：不断向上找父节点，直到找到根。
3. 合并集合：将两个集合的根节点连在一起。

为了优化效率，我们通常使用路径压缩。即在查找过程中，把沿途所有节点的父节点直接指向根节点，这样下次查找就是 O(1) 了。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], n, m;

// 查找根节点，带路径压缩
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    // 初始化：每个点自成一个集合
    for(int i = 1; i <= n; i++) p[i] = i;
    
    while(m--){
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(op[0] == 'M') {
            p[find(a)] = find(b); // 合并：让 a 的根指向 b 的根
        } else {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

进阶：统计集合大小

有时候我们需要知道每个集合里有多少个点。这时候只需维护一个 size 数组。合并时，将小集合的大小累加到大集合上即可。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], sizes[N], n, m;

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        sizes[i] = 1; // 初始大小为 1
    }
    
    while(m--){
        char op[5];
        int a, b;
        scanf("%s", op);
        if(op[0] == 'C') {
            scanf("%d%d", &a, &b);
            int rootA = find(a), rootB = find(b);
            if(rootA != rootB) {
                sizes[rootB] += sizes[rootA]; // 合并大小
                p[rootA] = rootB;
            }
        } else if(op[1] == '1') {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        } else {
            scanf("%d", &a);
            printf("%d\n", sizes[find(a)]);
        }
    }
    return 0;
}

掌握这三个结构，基本能覆盖大部分基础算法题的考点。实际编码时多注意边界条件和数组下标，就能避免很多不必要的错误。