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

KMP 算法

KMP 算法用于处理字符串匹配问题。给定主串 S[] 和模板串 P[]，通常使用下标 1 开始遍历。

暴力匹配

暴力方法在遇到不匹配字符时，P 串从头开始重新匹配 S 串的下一个位置。当串很长时容易超时。

for(int i = 1; i <= m; i ++){
    bool flag = true;
    for(int j = 1; j <= n; j++){
        if(S[i+j-1] != P[j]){
            flag = false;
            break;
        }
    }
}

原理

利用 P 串本身相同的前缀和后缀性质。当匹配失败时，无需逐个回退，直接跳到特定位置继续匹配。

next 数组

next[i] 表示以 i 为终点的后缀和从 1 开始的前缀相等的最长长度。 若 next[i] = j，则 p[1...j] = p[i-j+1...i]。

构造逻辑：假设 i-1 位置之前的最长前缀后缀长度为 j，若 S[i] == P[j+1]，则 j++，ne[i] = j；否则利用 ne[j] 回溯查找。

// 求 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;
}

匹配过程

指针 i 指向主串，j 指向模式串。若 S[i] != P[j+1]，j 回退到 ne[j]；若相等，j++。当 j==n 时匹配成功。

#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 树（字典树）用于快速存储和查找字符串集合。

核心思想：从根节点开始，将单词字母一一存入，最后一个字母做标记。cnt[p] 记录以当前点结尾的单词数量。

#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] 存储父节点。

• 判断树根：if(p[x] == x)
• 求集合编号：while(p[x] != x) x = p[x]
• 合并集合：p[find(x)] = find(y)

优化：路径压缩。

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

若需统计集合大小，可添加 size 数组。合并时 sizes[find(b)] += sizes[find(a)]。

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

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);
            if(find(a) == find(b)) continue;
            sizes[find(b)] += sizes[find(a)];
            p[find(a)] = find(b);
        } 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;
}