算法-KMP算法介绍

前言

字符串匹配算法的目的是在文本串 S 中找到与模式串 P 相匹配的起始索引 m。

最直接的算法被称为暴力（brute-force）算法，将模式串与文本串的每个可能的起始位置对齐，逐一比较模式串与文本串中对应的字符。如果发现不匹配，移动模式串到下一个位置，重新开始比较；如果模式串完全匹配，则找到了一个匹配位置。

暴力算法的时间复杂度是 $O(n*m)$，其中 $n$ 是文本串长度，$m$ 是模式串长度。在最坏情况下，对于每个可能的起始位置，都需要比较整个模式串。
因此暴力算法虽然直观，但在文本量大的情况下效率很低。本文将介绍一个效率更高的算法-KMP 算法

KMP 算法

KMP 算法是一种高效的字符串匹配算法，通过预处理模式串构建部分匹配表（next 数组），在匹配失败时利用已匹配信息跳过不必要的比较。

关键概念

最长前缀后缀数组：记录模式串中每个位置之前的最长相同前缀和后缀的长度。
前缀：不包含最后一个字符的连续子串。
后缀：不包含第一个字符的连续子串。

核心思想

部分匹配表（next 数组）：记录模式串每个前缀的最长公共前后缀长度。

匹配优化：当发生不匹配时，根据 next 数组调整模式串位置，避免回溯主串指针。

算法步骤

预处理阶段

计算 next 数组：

对模式串进行分析，构建最长前缀后缀数组
帮助在匹配失败时快速回退，避免重复比较

匹配阶段

使用 next 数组进行高效匹配：

逐字符比较文本串和模式串
当发生不匹配时，利用LPS数组快速移动模式串

代码实现

next 数组构建算法

以模式串 pattern = "ABABCABAB" 为例：

def build_next(pattern):
    # 初始化next数组，长度与pattern相同，初始值全部为0。
    # next数组存储了模式串pattern中子串的部分匹配值。
    next = [0] * len(pattern)
    
    # j是前缀末尾的指针，也是当前已经匹配的最大长度。
    j = 0  # 前缀末尾指针
    
    # i是后缀末尾的指针，从1开始遍历整个模式串。
    for i in range(1, len(pattern)):  # i是后缀末尾指针
        
        # 如果当前字符不匹配，则通过next[j-1]更新j值，
        # 直到找到匹配或者j退回到起始位置。
        while j > 0 and pattern[i] != pattern[j]:
            j = next[j-1]
        
        # 如果找到了匹配的字符，则增加j值，表示匹配长度加1。
        if pattern[i] == pattern[j]:
            j += 1
        
        # 更新next数组，记录下i位置的最大前后缀匹配长度。
        next[i] = j
    
    # 返回构建好的next数组。
    return next

模拟构建过程：

索引: 0 1 2 3 4 5 6 7 8
字符: A B A B C A B A B
next: 0 0 1 2 0 1 2 3 4

构建步骤：
i=1: j=0 → next[1]=0
i=2: p[2]=A=p[0] → j=1 → next[2]=1
i=3: p[3]=B=p[1] → j=2 → next[3]=2
i=4: p[4]=C≠p[2] → j=next[1]=0 → next[4]=0
i=5: p[5]=A=p[0] → j=1 → next[5]=1
i=6: p[6]=B=p[1] → j=2 → next[6]=2
i=7: p[7]=A=p[2] → j=3 → next[7]=3
i=8: p[8]=B=p[3] → j=4 → next[8]=4

KMP 匹配算法实现

def kmp_search(text, pattern):
    # 调用build_next函数构建模式串pattern的next数组，
    # next数组用于存储模式串中每个字符对应的最长相同前缀和后缀的长度。
    next = build_next(pattern)
    
    # j是模式串指针，初始化为0，指向模式串的起始位置。
    j = 0  # 模式串指针
    
    # i是主串指针，遍历整个主字符串text。
    for i in range(len(text)):  # 主串指针
        
        # 如果当前字符不匹配，并且模式串指针j已经前进（大于0），
        # 则根据next数组调整模式串指针j的位置，跳过不必要的比较。
        while j > 0 and text[i] != pattern[j]:
            j = next[j-1]
        
        # 如果找到了匹配的字符，则模式串指针j向前移动一位。
        if text[i] == pattern[j]:
            j += 1
            
            # 如果模式串完全匹配（即j等于模式串的长度），则返回匹配开始的位置。
            # i - j + 1计算的是匹配子串在主串中的起始索引。
            if j == len(pattern):
                return i - j + 1  # 匹配成功
    
    # 如果遍历完整个主串text都没有找到匹配项，则返回-1表示未找到匹配。
    return -1

算法模拟演示

输入：

1 2	text: "ABABDABACDABABCABAB" pattern: "ABABCABAB"

匹配过程：

步骤 | 主串位置 | 模式串位置 | 操作
-----|---------|-----------|--------------------
1   | i=0     | j=0       | 匹配成功，j=1
2   | i=1     | j=1       | 匹配成功，j=2
3   | i=2     | j=2       | 匹配成功，j=3
4   | i=3     | j=3       | 匹配成功，j=4
5   | i=4     | j=4       | 字符D≠C，j=next[3]=2
6   | i=4     | j=2       | 字符D≠A，j=next[1]=0
7   | i=4     | j=0       | 字符D≠A，i前进
...
当i=10时，最终完成完整匹配

算法分析

时间复杂度：$O(m+n)$，其中 $m$ 为模式串长度，$n$ 为主串长度。

空间复杂度：$O(m)$，用于存储 next 数组。

优势：相比暴力匹配的 $O(mn)$ 时间复杂度，显著提升效率。

深入分析

暴力算法的瓶颈问题

问题场景：在文本串 T[0...n-1] 中查找模式串 P[0...m-1]

暴力算法流程：

for i in 0...n-m:
    for j in 0...m-1:
        if T[i+j] != P[j]:
            break
    if j == m-1:
        return i

暴力算法的核心缺陷是每次失配时主串指针i完全回溯，浪费已匹配信息。

KMP的核心突破

已匹配部分的信息要怎么利用？

当 P[0...j-1] 与 T[i-j...i-1] 完全匹配，在位置 j 发生失配时：

已匹配区域： P[0] P[1] ... P[j-1]
                =    =        =
               T[i-j] T[i-j+1]...T[i-1]
失配位置：     P[j] ≠ T[i]

关键问题：如何最大化利用已匹配区域的信息，避免主串指针 i 回溯？

next 数组的数学定义

对于模式串 P，定义 next[j] 为子串 P[0...j] 的最长公共前后缀长度。

递推关系：

1	next[j] = max{ k \| P[0...k-1] = P[j-k...j-1] }

物理意义：当在 P[j] 失配时，模式串可以向右滑动 j - next[j-1] 位。

next数组正确性证明（数学归纳法）

定义：

对于模式串 $P[0\dots m-1]$，定义函数：
$$
f(j)=max{k|0≤k＜j且P[0\dots k-1]=P[j-k\dots j-1]}
$$
即子串 $P[0…j−1]$ 的最长公共前后缀长度。

需要证明：算法构建的 $next[j]=f(j)$

归纳基础：

当 $j=0$ 时，$next[0]=0$，空串的 LPS 长度为 0，成立。

归纳假设：

假设对于任意 $j ≤ n$，均有 $next[j] = f(j)$

归纳步骤：

需要证明 $next[n+1]=f(n+1)$

构建过程关键操作：

while j > 0 and pattern[i] != pattern[j]:
    j = next[j-1]
if pattern[i] == pattern[j]:
    j += 1
next[i] = j

分为两种情况讨论：

Case1：$P[i]=p[j]$

此时最长公共前后缀长度可扩展为 $j+1$
根据归纳假设，$j=f(i)$，因此 $f(i+1)=j+1$
算法执行 $j+=1$ 后赋值，正确性成立

Case2：$P[i]≠p[j]$

需找到次长的公共前后缀长度 $k=next[j-1]$
由数学归纳法，$next[j-1]=f(j-1)$
根据LPS的传递性，次长后缀必然由最长后缀的最长后缀构成。
通过循环回溯，最终找到最大的合法k值。

后缀链递减性：
若$P[0…k-1]=P[i-k…i-1]$，则次大的满足条件的$k^′$值为$next[k-1]$
证明：假设存在更大的$k^′$满足条件，则$P[0…k^′-1]$必须同时是$P[0…k-1]$的前缀和$P[i-k…i-1]$的后缀，这与$next[k-1]$定义矛盾。

匹配过程正确性证明（反证法）

命题：

KMP算法不会错过任何可能的匹配位置。

证明框架：

假设存在遗漏：
设存在某个有效匹配起始位置 $s$，但算法未能检测到。
矛盾构造：
设算法在某个时刻满足：
$$
i≥s+t，且j≥t
$$
其中 $t$ 是已经匹配的字符数。根据 LPS 定义，此时应有：
$$
t≤next[j−1]
$$
这意味着算法应该通过调整 $j=next[j-1]$ 来覆盖此情况，与假设矛盾。

详细推导：

假设在文本 $T$ 的 $pos$ 位置开始存在完整匹配，即：
$$
T[pos\dots pos+m-1] = P[0\dots m-1]
$$
但算法未能检测到该匹配。

观察算法行为：

当扫描到 $T[pos+j]$ 时（$0≤j≤m$），若发生失配，算法将调整模式串位置为 $next[j]$。
根据next数组的定义，此时新的起始位置为 $pos^′=pos+j-next[j-1]$

关键矛盾点：

若存在未被检测的匹配位置 $pos$，则必须存在某个 $j$ 使得：
$$
next[j-1]<实际存在的公共前后缀长度
$$

这与next数组记录最大值的定义矛盾。

后记

KMP算法相对于暴力算法来说时间复杂度得到了极大的提升，在各种情况下表现良好。