Day 17

kmp

KMP (Knuth-Morris-Pratt) 算法是一种高效的字符串匹配算法，用于在一个主字符串（文本 T）中查找一个模式字符串（P）的出现位置。

与朴素的暴力匹配算法相比，KMP 算法通过一个巧妙的预处理步骤，避免了不必要的字符比较，从而将时间复杂度从 O (N*M) 降低到了 O (N+M)，其中 N 是文本长度，M 是模式长度。

1. 核心思想

KMP 算法的核心思想是利用已经匹配过的信息，避免主串指针的回溯。

让我们通过一个例子来理解朴素算法的低效之处：

文本 T: BBC ABCDAB ABCDABCDABDE
模式 P: ABCDABD

朴素算法的过程：

BBC ABCDAB ABCDABCDABDEABCDABD^B 和 A 不匹配，模式右移一位。
BBC ABCDAB ABCDABCDABDEABCDABD^B 和 A 不匹配，模式右移一位。
BBC ABCDAB ABCDABCDABDEABCDABD^C 和 A 不匹配，模式右移一位。
BBC ABCDAB ABCDABCDABDEABCDABD^和 A 不匹配，模式右移一位。
BBC ABCDAB ABCDABCDABDEABCDABD^A 和 A 匹配，继续比较。
BBC ABCDAB ABCDABCDABDEABCDABD^B 和 B 匹配，继续比较。
BBC ABCDAB ABCDABCDABDEABCDABD^C 和 C 匹配，继续比较。
BBC ABCDAB ABCDABCDABDEABCDABD^D 和 D 匹配，继续比较。
BBC ABCDAB ABCDABCDABDEABCDABD^A 和 A 匹配，继续比较。
BBC ABCDAB ABCDABCDABDEABCDABD^B 和 B 匹配，继续比较。
BBC ABCDAB ABCDABCDABDEABCDABD^和 D 不匹配！

此时，朴素算法会将模式右移一位，然后主串指针 i 回溯到 i-j+1 的位置，模式指针 j 重置为 0，重新开始比较：

BBC ABCDAB ABCDABCDABDEABCDABD^这个过程非常低效，因为我们已经知道 AB 是匹配的，但又要重新比较。

KMP 算法的改进：

当第 11 步发生不匹配时，KMP 算法不会让主串指针 i 回溯。它会利用已经匹配的前缀 ABCDAB 的信息，直接将模式串 P 向右滑动一段距离，然后从模式的某个位置开始继续与主串的当前位置 i 进行比较。

2. 关键概念：部分匹配表 (Partial Match Table, PMT) 或最长公共前后缀 (Longest Prefix Suffix, LPS)

为了实现上述的 “智能滑动”，KMP 算法首先会对模式串 P 进行预处理，生成一个辅助数组，通常称为 next 数组（或 lps 数组）。

next[j] 的定义：对于模式串 P 的前 j+1 个字符组成的子串 P[0...j]，其最长相等的真前缀和真后缀的长度。

前缀 (Prefix)：除最后一个字符外，字符串的所有头部子串。例如，"ABCD" 的前缀是 ["A", "AB", "ABC"]。
后缀 (Suffix)：除第一个字符外，字符串的所有尾部子串。例如，"ABCD" 的后缀是 ["D", "CD", "BCD"]。
真 (Proper)：指不等于字符串本身的子串。

示例：计算模式 P = "ABCDABD" 的 next 数组

P[0...0] = "A": 没有真前缀和真后缀，next[0] = 0。
P[0...1] = "AB": 前缀 ["A"]，后缀 ["B"]。无公共部分，next[1] = 0。
P[0...2] = "ABC": 前缀 ["A", "AB"]，后缀 ["C", "BC"]。无公共部分，next[2] = 0。
P[0...3] = "ABCD": 前缀 ["A", "AB", "ABC"]，后缀 ["D", "CD", "BCD"]。无公共部分，next[3] = 0。
P[0...4] = "ABCDA": 前缀 ["A", "AB", "ABC", "ABCD"]，后缀 ["A", "DA", "CDA", "BCDA"]。最长公共部分是 "A"，长度为 1。next[4] = 1。
P[0...5] = "ABCDAB": 前缀 ["A", "AB", "ABC", "ABCD", "ABCDA"]，后缀 ["B", "AB", "DAB", "CDAB", "BCDAB"]。最长公共部分是 "AB"，长度为 2。next[5] = 2。
P[0...6] = "ABCDABD": 前缀 ["A", "AB", ..., "ABCDAB"]，后缀 ["D", "BD", ..., "BCDABD"]。无公共部分，next[6] = 0。

所以，模式 "ABCDABD" 的 next 数组为：[0, 0, 0, 0, 1, 2, 0]。

3. 算法步骤

KMP 算法分为两步：

构建 next 数组。
利用 next 数组进行匹配。

步骤一：构建 `next` 数组

这是一个递推的过程。

cpp

运行

// s 是模式串
void buildNext(const string& s, vector<int>& next) {
    int n = s.size();
    next.resize(n, 0);
    int j = 0; // j 指向前缀的末尾

    // i 从 1 开始，指向后缀的末尾
    for (int i = 1; i < n; ++i) {
        // 情况1：s[i] != s[j]，回退 j
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        // 情况2：s[i] == s[j]，匹配成功，j 前进
        if (s[i] == s[j]) {
            j++;
        }
        // 更新 next[i]
        next[i] = j;
    }
}

步骤二：利用 `next` 数组进行匹配

cpp

运行

// t 是文本串, p 是模式串, next 是模式串的 next 数组
int kmpSearch(const string& t, const string& p, const vector<int>& next) {
    int n = t.size();
    int m = p.size();
    int j = 0; // j 是模式串的指针

    // i 是文本串的指针，它不会回退
    for (int i = 0; i < n; ++i) {
        // 情况1：t[i] != p[j]，利用 next 数组回退模式串指针 j
        while (j > 0 && t[i] != p[j]) {
            j = next[j - 1];
        }
        // 情况2：t[i] == p[j]，匹配成功，j 前进
        if (t[i] == p[j]) {
            j++;
        }
        // 情况3：j == m，说明模式串完全匹配
        if (j == m) {
            // 返回匹配的起始索引
            return i - m + 1;
        }
    }
    // 未找到匹配
    return -1;
}

4. C++ 完整实现

cpp

运行

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

using namespace std;

/**
 * @brief 构建 KMP 算法的 next 数组 (最长公共前后缀数组)
 * @param pattern 模式串
 * @param next 用于存储结果的 next 数组
 */
void buildNext(const string& pattern, vector<int>& next) {
    int n = pattern.size();
    next.resize(n, 0);
    int j = 0; // j 指向前缀的末尾

    // i 从 1 开始，指向后缀的末尾
    for (int i = 1; i < n; ++i) {
        // 1. 当 pattern[i] != pattern[j] 时，回退 j
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        // 2. 当 pattern[i] == pattern[j] 时，j 前进
        if (pattern[i] == pattern[j]) {
            j++;
        }
        // 3. 更新 next[i]
        next[i] = j;
    }
}

/**
 * @brief 使用 KMP 算法在文本串中查找模式串
 * @param text 文本串
 * @param pattern 模式串
 * @return int 如果找到，返回第一个匹配的起始索引；否则返回 -1
 */
int kmpSearch(const string& text, const string& pattern) {
    int n = text.size();
    int m = pattern.size();

    if (m == 0) return 0;
    if (n < m) return -1;

    vector<int> next;
    buildNext(pattern, next);

    int j = 0; // j 是模式串的指针
    // i 是文本串的指针，它不会回退
    for (int i = 0; i < n; ++i) {
        // 1. 当 text[i] != pattern[j] 时，利用 next 数组回退模式串指针 j
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        // 2. 当 text[i] == pattern[j] 时，j 前进
        if (text[i] == pattern[j]) {
            j++;
        }
        // 3. 如果 j == m，说明模式串完全匹配
        if (j == m) {
            // 返回匹配的起始索引
            return i - m + 1;
        }
    }

    // 遍历完文本串仍未找到匹配
    return -1;
}

int main() {
    string text = "BBC ABCDAB ABCDABCDABDE";
    string pattern = "ABCDABD";

    cout << "文本串: " << text << endl;
    cout << "模式串: " << pattern << endl;
    cout << "---------------------------------" << endl;

    vector<int> next;
    buildNext(pattern, next);

    cout << "模式串 \"" << pattern << "\" 的 next 数组为: ";
    for (int val : next) {
        cout << val << " ";
    }
    cout << endl << "---------------------------------" << endl;

    int index = kmpSearch(text, pattern);

    if (index != -1) {
        cout << "匹配成功！" << endl;
        cout << "模式串在文本串中的起始索引为: " << index << endl;
        cout << "匹配的子串是: " << text.substr(index, pattern.size()) << endl;
    } else {
        cout << "匹配失败，文本串中未找到模式串。" << endl;
    }

    return 0;
}

运行结果

plaintext

文本串: BBC ABCDAB ABCDABCDABDE
模式串: ABCDABD
---------------------------------
模式串 "ABCDABD" 的 next 数组为: 0 0 0 0 1 2 0 
---------------------------------
匹配成功！
模式串在文本串中的起始索引为: 15
匹配的子串是: ABCDABD