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

C++算法

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

深入解析 KMP 字符串匹配算法、Trie 前缀树及并查集数据结构。涵盖暴力匹配优化思路、Next 数组构建原理、Trie 插入查询实现以及并查集路径压缩优化。提供完整 C++ 代码模板，适合算法学习与实战参考。

深海蔚蓝发布于 2026/3/21更新于 2026/5/128 浏览

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

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

在算法竞赛和工程实践中，高效的数据结构往往是解决问题的关键。本文将深入解析三种经典且实用的数据结构：KMP 字符串匹配算法、Trie 前缀树以及并查集。我们将通过原理剖析与代码实现，帮助读者建立清晰的逻辑框架。

KMP 算法

KMP（Knuth-Morris-Pratt）算法主要用于解决字符串匹配问题。相比于暴力匹配，它能在 O(n+m) 的时间复杂度内完成搜索，避免了不必要的回溯。

原理

暴力匹配的思路是：当主串 S 的某一位与模式串 P 不匹配时，P 从头开始重新匹配 S 的下一位。这会导致大量重复比较。

KMP 的核心思想在于利用模式串本身的性质。如果 P 的前缀和后缀存在相同的部分，当匹配失败时，我们可以直接将 P 滑动到下一个可能匹配的位置，而无需回退 S 的指针。关键在于如何确定这个滑动位置，这就是 next 数组的作用。

文章配图

Next 数组

next[i] 表示以 i 为终点的最长公共前后缀的长度。具体来说，若 next[i] = j，则意味着 P[1...j] == P[i-j+1...i]。

构建 next 数组的过程类似于 KMP 匹配过程本身。我们假设已知 next[i-1] 的值，尝试扩展当前匹配长度。如果当前位置字符不匹配，则利用已知的 next 值进行回溯，直到找到匹配或回到起点。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
char P[N];
int ne[N], n; // ne 数组即 next 数组

int main(){
    cin >> n >> (P + 1); // 1-based indexing
    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;
    }
    return 0;
}

匹配过程

#include<iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10;
char S[M], P[N];
int ne[N], 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;
}

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

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