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

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]; // 继续寻找下一个匹配
    }
}

下面是完整的 C++ 模板，注意变量定义中 n 为模式串长度，m 为主串长度：

#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);
    
    // 求 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;
    }
    
    // 匹配过程
    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 树（字典树）是一种专门用于高效存储和检索字符串集合的数据结构。它的核心优势在于利用公共前缀减少存储空间，查询效率与字符串长度相关，而与集合大小无关。

结构与操作

每个节点代表一个字符，从根节点出发的一条路径构成一个单词。我们在单词结束的位置做标记，以便区分不同长度的单词。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
char str[N];
int son[N][26], cnt[N], idx;

// 插入操作
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;
}

并查集

并查集主要用于处理不相交集合的合并与查询问题。它支持两种基本操作：合并两个集合，以及判断两个元素是否属于同一集合。

基本原理

每个集合用一棵树表示，树根即为集合的代表元素。通过父节点数组 p[x] 来维护父子关系。初始状态下，每个元素都是独立的集合，即 p[i] = i。

核心实现

查找根节点时，我们可以使用路径压缩优化，将查找路径上的所有节点直接指向根节点，从而大幅降低后续查询的时间复杂度。

#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); // 合并
        else {
            puts(find(a) == find(b) ? "Yes" : "No");
        }
    }
    return 0;
}

扩展应用

如果需要统计每个集合的大小，可以额外维护一个 size 数组。合并时将小集合的 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;
    }
    
    while(m--){
        char op[5];
        int a, b;
        scanf("%s", op);
        if(op[0] == 'C') {
            scanf("%d%d", &a, &b);
            int ra = find(a), rb = find(b);
            if(ra != rb) {
                sizes[rb] += sizes[ra];
                p[ra] = rb;
            }
        } else if(op[1] == '1') {
            scanf("%d%d", &a, &b);
            puts(find(a) == find(b) ? "Yes" : "No");
        } else {
            scanf("%d", &a);
            printf("%d\n", sizes[find(a)]);
        }
    }
    return 0;
}