数据结构核心：KMP 算法、Trie 树与并查集详解 | 极客日志

C++算法

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

KMP 算法通过构建 next 数组优化字符串匹配，避免暴力回溯，将复杂度降至线性。Trie 树利用前缀共享特性，实现高效的字符串存储与检索。并查集通过树形结构与路径压缩，快速处理集合合并及连通性判断。三者均为算法竞赛与工程实践中的核心工具，配合 C++ 实现可显著提升数据处理性能。

未来可期发布于 2026/3/26更新于 2026/4/251 浏览

数据结构核心：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(, i - n); 
            j = ne[j]; 
        }
    }
     ;
}

#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;
}

#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;
}

#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;
}