KMP算法核心：next数组构建与优化实战

1. 字符串匹配算法中的KMP核心思想

KMP算法作为字符串匹配领域的经典算法，其核心在于通过预处理模式串构建next数组，实现匹配失败时的智能跳转。传统暴力匹配算法在每次失配时都需要回溯主串指针，时间复杂度高达O(mn)。而KMP算法通过next数组记录模式串的自匹配信息，将时间复杂度优化至O(m+n)。

在实际教学和工程实践中，我发现很多学习者对next数组的理解停留在表面，特别是对nextval优化版本和滑动距离计算原理存在认知盲区。这正是统考真题常考的核心难点，也是区分算法掌握程度的关键指标。

2. next数组的构建原理与手工计算

2.1 基本next数组定义

next数组的每个元素next[i]表示模式串P[0...i]这个子串中，使得前k个字符与后k个字符相等的最大的k（k不能等于i+1，否则没有滑动意义）。数学表达式为：

code复制next[i] = max{k | 0≤k<i 且 P[0...k-1] = P[i-k...i-1]}

以模式串"ababaa"为例，手工计算next数组的过程如下：

1. next[0] = -1 （约定首字符next值为-1）
2. next[1] = 0 （"a"无真前缀后缀）
3. next[2] = 0 （"ab"前后缀无匹配）
4. next[3] = 1 （"aba"最长匹配前后缀"a"，长度1）
5. next[4] = 2 （"abab"最长匹配前后缀"ab"，长度2）
6. next[5] = 3 （"ababa"最长匹配前后缀"aba"，长度3）

注意：不同教材对next数组起始值定义可能不同（有-1起始和0起始两种主流定义），实际算法实现时需保持一致。

2.2 next数组的编程实现

python复制def build_next(pattern):
    next = [-1] * len(pattern)
    i, j = 0, -1
    while i < len(pattern) - 1:
        if j == -1 or pattern[i] == pattern[j]:
            i += 1
            j += 1
            next[i] = j