算法——KMP算法（Knuth-Morris-Pratt算法）

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，用于在主文本字符串中快速查找模式字符串的出现位置。其核心思想是通过预处理模式字符串，利用部分匹配信息（即“失败函数”或“next数组”）避免在匹配失败时回溯主串，从而将时间复杂度优化到 O(n+m)（n是主串长度，m是模式串长度），远优于暴力匹配算法的 O(n×m)。

一，核心原理

1. 部分匹配表（Prefix Table / Next数组）

   • 定义：next[i] 表示模式串的子串 P[0...i] 的最长公共前后缀长度。
   • 作用：当字符匹配失败时，根据 next 数组决定模式串的回溯位置，避免重复比较主串。

2. 匹配过程

   • 主串指针不回溯，仅移动模式串指针：
     若当前字符匹配失败，模式串指针回退到 next[j] 的位置继续匹配。

二，Next数组的构建

最长前缀概念： 最长前缀是说以第一个字符开始，但是不包含最后一个字符。
最长后缀概念： 最长后缀是说以最后一个字符开始，但是不包含第一个字符。
next 数组定义：在模式串中（下标从0开始），next[i] 表示模式串中以下标 i 处字符结尾的子串的最大相同前后缀的长度。在KMP算法中，该值一方面表示模式串中1~i位置子串中的最长相同前后缀长度，另一方面表示在该位置匹配失败时模式串回溯比较的下一个字符位置（最长前缀末座标的下一个字符）

步骤示例（模式串 P = "ABABCABAB"）

最终 next = [0, 0, 1, 2, 0, 1, 2, 3, 4]。

构建代码（Python）

def build_next(pattern):
    next = [0] * len(pattern)
    j = 0  # 前缀末尾指针
    for i in range(1, len(pattern)):  # 后缀末尾指针
        while j > 0 and pattern[i] != pattern[j]:
            j = next[j-1]  # 回退到前一个匹配位置
        if pattern[i] == pattern[j]:
            j += 1
        next[i] = j
    return next

# 示例：模式串 "ABABCABAB"
print(build_next("ABABCABAB"))  # 输出 [0, 0, 1, 2, 0, 1, 2, 3, 4]

三，匹配过程代码（Python）

def kmp_search(text, pattern):
    next = build_next(pattern)
    j = 0  # 模式串指针
    for i in range(len(text)):  # 主串指针
        while j > 0 and text[i] != pattern[j]:
            j = next[j-1]  # 模式串回退
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1  # 返回匹配的起始位置
    return -1

# 示例
text = "ABABABCABABABD"
pattern = "ABABCABAB"
print(kmp_search(text, pattern))  # 输出 2（从索引2开始匹配）

多次出现的位置

def kmp_search(text, pattern):
    index = [] 
    next = build_next(pattern)
 
    j = 0  # 模式串指针
    for i in range(len(text)):  # 主串指针
        while j > 0 and text[i] != pattern[j]:
            j = next[j-1]  # 模式串回退
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            #return i - j + 1  # 返回匹配的起始位置
            index.append(i - j + 1)
            j = next[j-1]
            
    return index

匹配失败时：失败位置之前的主串（i前）和子串（j前）部分一定都是匹配的。且对于子串来说，失败位置之前（j前）的任一部分属于子串（模式串）的这段子串（子子串）的后缀
重新匹配时：我们重新匹配的开始一定是子串（模式串）的某部分前缀
要想移动子串（模式串）指针（i 下次匹配位置）到最大有效匹配位置，那么这个位置一定是这段前缀=后缀的部分

四，关键点

1. 时间复杂度

   • 预处理模式串构建 next 数组：O(m)
   • 匹配过程：O(n)
   • 总体：O(n + m).

2. 优势

   • 避免主串指针回溯，适合处理大文本流或实时数据。

3. 应用场景

   • 文本编辑器中的查找功能（如Ctrl+F）、代码解析、DNA序列匹配等。

无，对比暴力匹配

• 暴力匹配：每次失配后，主串和模式串指针均回退，重复比较已匹配的字符。

  主串：A B A B A B C
  模式：A B A B C
  暴力匹配需要回退主串指针，比较多次。
  

• KMP：主串指针不回溯，仅调整模式串指针，效率显著提升。

掌握KMP算法的核心在于理解部分匹配表的构建逻辑和失配时的回溯策略。