数据结构：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;

 {
    cin >> n >> (P + ) >> m >> (S + );
    
    ( i = , j = ; i <= n; i ++){
        (j && P[i] != P[j + ]) j = ne[j];
        (P[i] == P[j + ]) j ++;
        ne[i] = j;
    }
    
    ( i = , j = ; i <= m; i ++){
        (j && S[i] != P[j + ]) j = ne[j];
        (S[i] == P[j + ]) j ++;
        (j == n){
            (, i - n);
            j = ne[j];
        }
    }
     ;
}