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

在处理字符串匹配与集合管理问题时，暴力解法往往效率低下。本文深入解析 KMP 算法、Trie 树及并查集的核心原理与 C++ 实现。相比传统方法，这些结构能显著降低时间复杂度，是算法竞赛与工程实践中的必备工具。

KMP 算法

KMP 主要用于解决主串 S 中查找模板串 P 的问题。暴力匹配在字符不匹配时会回退主串指针，导致 O(n*m) 的时间复杂度。KMP 的核心在于利用已匹配部分的信息，避免不必要的回溯。

关键在于 next 数组（或称前缀表）。next[i] 表示以 i 结尾的子串中，最长相等前后缀的长度。当匹配失败时，根据 next 数组调整 P 串的位置，无需移动 S 串指针。很多人对 next 数组感到困惑，其实它本质上就是找最长公共前后缀。

构造 next 数组时，我们维护一个指针 j 表示当前匹配的前缀长度。若 P[i] == P[j+1]，则 j 加一；否则利用 next[j] 回溯 j，直到匹配成功或 j 归零。这里要注意，代码中通常使用 1-based 索引来简化逻辑。

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
char S[N], P[N];
int ne[N]; // next 数组

int main() {
    int n, m;
    cin >> n >> (P + 1) >> m >> (S + 1); // 1-based 索引

    // 求 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 树（字典树）是一种专门用于存储字符串集合的数据结构。它通过共享公共前缀来节省空间，查询效率取决于字符串长度而非集合大小。想象一下，如果我们要存几万个单词，普通哈希表可能冲突，Trie 树就能完美解决。

每个节点代表一个字符，从根节点出发，路径即为单词。通常用二维数组 son[u][c] 存储子节点，cnt[u] 记录以该节点结尾的单词数量。插入和查询操作都是沿着字符路径走一遍即可。

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
char str[N];
int son[N][26], cnt[N], idx; // 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] 存储 x 的父节点。为了优化性能，引入路径压缩：在 find 操作中，将沿途节点的父节点直接指向根节点。这样后续查询会非常快。

#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 累加到大集合上。实际运行中，记得初始化 size 为 1。

#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);
            puts(find(a) == find(b) ? "Yes" : "No");
        } else {
            scanf("%d", &a);
            printf("%d\n", sizes[find(a)]);
        }
    }
    return 0;
}