字符串算法：KMP 算法详解

什么是 KMP 算法？

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主文本串 S 中查找一个模式串 P 的出现位置。它的核心优势在于，当匹配过程中发生不一致时，它能利用已经匹配过的信息，跳过一些不必要的比较，从而避免了暴力匹配中的指针回溯，将时间复杂度优化到线性 O(n+m)。

核心思想：next 数组

KMP 算法的精髓在于一个预处理过的 next 数组（有时也叫 lps 数组，表示最长公共前后缀 Longest Proper Prefix which is also Suffix）。next[i] 存储的是模式串 P 的子串 P[0...i] 中，最长的相等的前缀和后缀的长度。

例如，对于模式串 P = "ababaca"：

• next[0] = 0 (a)
• next[1] = 0 (ab)
• next[2] = 1 (aba, 前缀 a == 后缀 a)
• next[3] = 2 (abab, 前缀 ab == 后缀 ab)
• next[4] = 3 (ababa, 前缀 aba == 后缀 aba)
• next[5] = 0 (ababac)
• next[6] = 1 (ababaca, 前缀 a == 后缀 a)

这个 next ���组告诉我们，在匹配失败时，模式串应该向右“滑动”多少位，才能让模式串的前缀与刚刚匹配成功的部分对齐，从而继续比较。

算法流程

1. 预处理: 计算模式串 P 的 next 数组。
2. 匹配:
   • 使用两个指针，i 遍历主文本串 S，j 遍历模式串 P。
   • 如果 S[i] == P[j]，则 i 和 j 一起前进。
   • 如果 S[i] != P[j]，主文本串的指针 i 不动，模式串的指针 j 回溯到 next[j-1] 的位置，然后继续与 S[i] 比较。这相当于将模式串向右滑动了 j - next[j-1] 位。
   • 如果 j 已经回溯到 0 仍然不匹配，则 i 前进一位，从头开始匹配。
   • 当 j 到达模式串末尾时，说明找到了一个完整的匹配。

C++ 代码实现

#include <iostream>
#include <string>
#include <vector>

// 计算 next 数组
std::vector<int> computeNext(const std::string& p) {
    int m = p.length();
    std::vector<int> next(m, 0);
    for (int i = 1, length = 0; i < m; ) {
        if (p[i] == p[length]) {
            length++;
            next[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = next[length - 1];
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}

// KMP 搜索
void kmpSearch(const std::string& s, const std::string& p) {
    int n = s.length();
    int m = p.length();
    std::vector<int> next = computeNext(p);
    int i = 0; // 指向 s
    int j = 0; // 指向 p
    while (i < n) {
        if (p[j] == s[i]) {
            i++;
            j++;
        }
        if (j == m) {
            std::cout << "Found pattern at index " << i - j << std::endl;
            j = next[j - 1];
        } else if (i < n && p[j] != s[i]) {
            if (j != 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }
}

KMP 算法是字符串处理的基础，理解其 next 数组的原理是掌握它的关键。