KMP算法

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

很多KMP算法的时间都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢？

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

其实这并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

C++

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

using namespace std;

// 计算模式串 pattern 的 next 数组
vector<int> getNext(string pattern) {
    int len = pattern.length(); // 计算模式串的长度
    vector<int> next(len, 0); // 初始化 next 数组，全部赋值为 0
    int j = 0; // j 表示当前比较的位置
    for (int i = 1; i < len; i++) { // i 表示当前需要计算 next 值的位置
        while (j > 0 && pattern[i] != pattern[j]) { // 如果当前字符不匹配，则向前跳
            j = next[j - 1]; // next[j-1] 表示当前字符之前的字符串的最长公共前缀和后缀的长度
        }
        if (pattern[i] == pattern[j]) { // 如果当前字符匹配，则继续向后比较
            j++; // 比较下一个字符
        }
        next[i] = j; // 更新 next 数组
    }
    return next; // 返回计算好的 next 数组
}

// 在文本串 text 中查找模式串 pattern
int kmp(string text, string pattern) {
    int n = text.length(); // 计算文本串的长度
    int m = pattern.length(); // 计算模式串的长度
    if (m == 0) { // 特判，模式串为空串
        return 0; // 在文本串的位置 0 处匹配
    }
    if (n < m) { // 特判，文本串比模式串短
        return -1; // 没有匹配的位置，返回 -1
    }
    vector<int> next = getNext(pattern); // 计算模式串的 next 数组
    int j = 0; // j 表示当前在模式串中比较的位置
    for (int i = 0; i < n; i++) { // i 表示当前在文本串中比较的位置
        while (j > 0 && text[i] != pattern[j]) { // 如果当前字符不匹配，则向前跳
            j = next[j - 1]; // next[j-1] 表示当前字符之前的字符串的最长公共前缀和后缀的长度
        }
        if (text[i] == pattern[j]) { // 如果当前字符匹配，则继续向后比较
            j++; // 比较下一个字符
        }
        if (j == m) { // 如果 j 等于 m，表示模式串已经完全匹配
            return i - m + 1; // 返回匹配的位置，即文本串中的起始位置
        }
    }
    return -1; // 没有匹配的位置，返回 -1
}

int main() {
    string text = "hello world";// 定义文本串
    string pattern = "world";// 定义模式串
    int index = kmp(text, pattern); // 在文本串中查找
    if (index == -1) {
        cout << "pattern not found" << endl;
    } else {
        cout << "pattern found at index " << index << endl;
    }
    return 0;
}

Python

def get_next(pattern: str) -> List[int]:
    """计算模式串 pattern 的 next 数组"""
    m = len(pattern)
    next = [0] * m  # 初始化 next 数组，全部赋值为 0
    j = 0  # j 表示当前比较的位置
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:  # 如果当前字符不匹配，则向前跳
            j = next[j-1]  # next[j-1] 表示当前字符之前的字符串的最长公共前缀和后缀的长度
        if pattern[i] == pattern[j]:  # 如果当前字符匹配，则继续向后比较
            j += 1  # 比较下一个字符
        next[i] = j  # 更新 next 数组
    return next  # 返回计算好的 next 数组


def kmp(text: str, pattern: str) -> int:
    """在文本串 text 中查找模式串 pattern"""
    n, m = len(text), len(pattern)
    if m == 0:  # 特判，模式串为空串
        return 0  # 在文本串的位置 0 处匹配
    if n < m:  # 特判，文本串比模式串短
        return -1  # 没有匹配的位置，返回 -1
    next = get_next(pattern)  # 计算模式串的 next 数组
    j = 0  # j 表示当前在模式串中比较的位置
    for i in range(n):  # i 表示当前在文本串中比较的位置
        while j > 0 and text[i] != pattern[j]:  # 如果当前字符不匹配，则向前跳
            j = next[j-1]  # next[j-1] 表示当前字符之前的字符串的最长公共前缀和后缀的长度
        if text[i] == pattern[j]:  # 如果当前字符匹配，则继续向后比较
            j += 1  # 比较下一个字符
        if j == m:  # 如果 j 等于 m，表示模式串已经完全匹配
            return i - m + 1  # 返回匹配的位置，即文本串中的起始位置
    return -1  # 没有匹配的位置，返回 -1


# 测试
text = "hello world"  # 定义文本串
pattern = "world"  # 定义模式串
pos = kmp(text, pattern)  # 在文本串中查找模式串
if pos == -1:
    print("在文本串中未找到模式串")
else:
    print(f"在文本串的第 {pos} 个位置找到了模式串")