数据结构详解:KMP 算法、Trie 树与并查集
KMP 算法
KMP 算法主要用于解决字符串匹配问题。给定主串 S[](较长)和模式串 P[],KMP 算法通常使用下标从 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 从头开始,但 P 串本身存在相同的前缀和后缀。当匹配失败时,无需逐个回退,可直接跳到特定位置继续匹配。

Next 数组
Next 数组的含义是以 i 为终点的后缀和从 1 开始的前缀相等的最长长度。
即 next[i] = j 表示 P[1...j] == P[i-j+1...i]。
计算方法:假设 i-1 位置之前的最长前缀后缀长度为 j,若 P[i] == P[j+1],则 j++,令 next[i] = j;否则利用 next[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;
}
匹配过程
明确指针后,每次比较 j+1 和 i 位置是否相同。不同则 j 回退到 ne[j],相同则 j++。
// KMP 匹配模板
#include<iostream>
using namespace std;
N = + ;
M = + ;
S[M], P[N], ne[N];
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];
}
}
;
}




