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

数据结构详解：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];
        }
    }
     ;
}