KMP 字符串匹配算法

原理介绍

KMP 算法是一种高效的字符串匹配算法，其核心思想是利用已经匹配过的部分避免主串指针回溯，将时间复杂度由朴素匹配的 O(n*m) 降至 O(n+m)。

next 数组的定义

next[i] 表示模式串 P[0 ... i] 这个子串中，最长的相等前缀和后缀的长度（前缀不能为整个子串）。

例如：P = "ababc"

  • next[0] = 0（单字符无真前后缀）
  • next[1] = 0（”ab” 无相等前后缀）
  • next[2] = 1（”aba” 前缀 “a”，后缀 “a”）
  • next[3] = 2（”abab” 前缀 “ab”，后缀 “ab”）
  • next[4] = 0（”ababc” 无相等前后缀）

当匹配失败时，next[i-1] 告诉我们可以跳过多少个字符继续匹配，避免主串指针回退。

算法流程

  1. 构建 next 数组
    通过双指针 i（后缀末尾）和 j（前缀长度）遍历模式串，若不匹配，j 回退到 next[j-1]。
  2. 匹配过程
    主串指针 i 和模式串指针 k 依次比较，失配时 k 回退到 next[k-1]，匹配成功时记录起始位置，并继续查找下一个匹配。

以下附上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
vector<int> nxt;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    // 1. 构建 next 数组
    int j = 0;                     // j 表示当前相等前缀的长度
    nxt.assign(m, 0);
    for (int i = 1; i < m; i++) {  // i 从 1 开始，子串 [0..i]
        while (j > 0 && b[i] != b[j]) 
            j = nxt[j - 1];
        if (b[i] == b[j]) 
            j++;
        nxt[i] = j;
    }
    // 2. 匹配过程
    int k = 0;                     // 模式串指针
    for (int i = 0; i < n; i++) {  // 主串指针 i
        while (k > 0 && a[i] != b[k]) 
            k = nxt[k - 1];
        if (a[i] == b[k]) 
            k++;
        if (k == m) {              // 匹配成功
            cout << i - m + 2 << ' '; 
            k = nxt[k - 1];       
        }
    }
    return 0;
}