算法代码示例

def compute_next(pattern):
    """计算模式串的next数组"""
    m = len(pattern)
    next_array = [0] * m  # 初始化next数组，长度等于模式串长度
    j = 0  # j表示当前最长相等前缀的末尾索引

    # 从第1个字符（i=1）开始遍历模式串
    for i in range(1, m):
        # 当j>0且当前字符不匹配时，j回退到next[j-1]
        while j > 0 and pattern[i] != pattern[j]:
            j = next_array[j-1]
        # 如果当前字符匹配，j和i同时后移
        if pattern[i] == pattern[j]:
            j += 1
        # 记录i位置的next值
        next_array[i] = j
    return next_array
def kmp_search(main_str, pattern, next_array):
    """使用KMP算法在主串中查找模式串的所有起始位置"""
    n = len(main_str)
    m = len(pattern)
    j = 0  # 模式串的当前匹配位置
    result = []  # 保存所有匹配的起始索引
    for i in range(n):
        # 当j>0且当前字符不匹配时，j回退到next[j-1]
        while j > 0 and main_str[i] != pattern[j]:
            j = next_array[j-1]
        # 如果当前字符匹配，j和i同时后移
        if main_str[i] == pattern[j]:
            j += 1
        # 如果模式串完全匹配（j等于模式串长度）
        if j == m:
            result.append(i - m + 1)  # 记录匹配的起始位置（i是模式串末尾，起始位置是i-m+1）
            j = next_array[j-1]  # 回退j，继续查找下一个可能的匹配
    return result
# 示例测试
if __name__ == "__main__":
    main_str = "ABABABCABAB"
    pattern = "ABABC"
    next_array = compute_next(pattern)
    positions = kmp_search(main_str, pattern, next_array)
    print(f"模式串 '{pattern}' 在主串 '{main_str}' 中的匹配位置为：{positions}")  # 输出：[2]
    

推导

要理解KMP算法的next数组，我们需要从最长相等前缀和后缀的概念入手，并通过具体示例演示推导过程。以下是详细的推导步骤：

一、核心概念：前缀、后缀与最长相等前后缀

在模式串中，对于位置i（从0开始计数），我们关注的是子串pattern[0...i]（即前i+1个字符）的前缀和后缀：

• 前缀：子串的所有真前缀（不包含最后一个字符的子串）。例如，子串"ABA"的前缀是"A"、"AB"。
• 后缀：子串的所有真后缀（不包含第一个字符的子串）。例如，子串"ABA"的后缀是"A"、"BA"。
• 最长相等前后缀：前缀和后缀中最长且完全相等的子串的长度。例如，子串"ABA"的前缀"A"和后缀"A"相等，长度为1，因此最长相等前后缀长度为1。

二、next数组的定义

next[i]表示模式串中子串pattern[0...i]的最长相等前后缀的长度。
例如，模式串"ABABC"的next数组为[0, 0, 1, 2, 0]（具体推导见下文）。

三、next数组的推导示例（以模式串"ABABC"为例）

我们通过逐位置分析模式串"ABABC"（索引0~4），推导每个位置的next[i]值。

步骤1：初始化next数组

模式串长度为5（索引0~4），因此next数组长度为5，初始化为[0, 0, 0, 0, 0]。

步骤2：逐个计算next[i]的值

我们从i=0开始，逐步推导到i=4：

详细解释每个位置的推导：

• i=0（子串"A"）：
  没有真前缀（因为子串长度为1，真前缀为空），也没有真后缀。最长相等前后缀长度为0 → next[0] = 0。
• i=1（子串"AB"）：
  真前缀是"A"，真后缀是"B"。两者不相等 → 最长相等前后缀长度为0 → next[1] = 0。
• i=2（子串"ABA"）：
  真前缀是"A"、"AB"；真后缀是"A"、"BA"。

其中，"A"（前缀）和"A"（后缀）相等，长度为1 → 最长相等前后缀长度为1 → next[2] = 1。

• i=3（子串"ABAB"）：
  真前缀是"A"、"AB"、"ABA"；真后缀是"B"、"AB"、"BAB"。

其中，"AB"（前缀）和"AB"（后缀）相等，长度为2 → 最长相等前后缀长度为2 → next[3] = 2。

• i=4（子串"ABABC"）：
  真前缀是"A"、"AB"、"ABA"、"ABAB"；真后缀是"C"、"BC"、"ABC"、"BABC"。

所有前缀和后缀均不相等 → 最长相等前后缀长度为0 → next[4] = 0。

四、用代码推导next数组的逻辑（关键步骤）

前面的示例是手动推导，实际代码中需要高效计算next数组。以下是compute_next函数的核心逻辑（结合模式串"ABABC"）：

代码逻辑分解（以"ABABC"为例）

def compute_next(pattern):
    m = len(pattern)
    next_array = [0] * m  # 初始化next数组为[0,0,0,0,0]
    j = 0  # j表示当前最长相等前缀的末尾索引（初始为0）

    for i in range(1, m):  # i从1开始（i=1~4）
        # 当j>0且当前字符不匹配时，j回退到next[j-1]
        while j > 0 and pattern[i] != pattern[j]:
            j = next_array[j-1]
        # 如果当前字符匹配，j和i同时后移
        if pattern[i] == pattern[j]:
            j += 1
        # 记录i位置的next值
        next_array[i] = j
    return next_array

逐次迭代过程（以"ABABC"为例）

五、next数组的关键性质

1. 利用已计算的next值避免重复比较：
   当pattern[i] != pattern[j]时，j回退到next[j-1]（即前一个位置的最长相等前后缀长度），这是因为前一个位置的最长相等前后缀已经保证了部分匹配的有效性，无需从头开始比较。
2. next数组的递增性：
   在大多数情况下，next[i]的值不会超过next[i-1]+1，因为最长相等前后缀的长度是逐步增加的（除非遇到不匹配的字符）。

六、为什么next数组能优化匹配？

当主串和模式串在位置i（主串）和j（模式串）匹配失败时：

• 暴力算法会将主串指针回退到i-j+1，模式串指针重置为0。
• KMP算法通过next[j-1]直接将模式串指针跳转到next[j-1]，主串指针无需回溯（因为pattern[0...next[j-1]-1]已经与主串的i-next[j-1]...i-1]匹配）。

总结

next数组的推导核心是寻找模式串每个子串的最长相等前后缀，其计算过程通过动态规划思想（利用已计算的next值避免重复比较）实现高效推导。理解这一过程后，KMP算法的匹配逻辑将变得清晰——通过next数组跳过不必要的比较，将时间复杂度优化到线性。

kmp_search函数定义与参数

def kmp_search(main_str, pattern, next_array):
    """使用KMP算法在主串中查找模式串的所有起始位置"""

• kmp_search 是函数名。
• main_str 是主串，也就是要在其中查找模式串的字符串。
• pattern 是模式串，即要查找的目标字符串。
• next_array 是通过 compute_next 函数计算出的模式串的 next 数组，其用途是在匹配失败时指导模式串指针的回退。

初始化变量

    n = len(main_str)
    m = len(pattern)
    j = 0  # 模式串的当前匹配位置
    result = []  # 保存所有匹配的起始索引

• n 代表主串的长度。
• m 代表模式串的长度。
• j 表示模式串当前正在匹配的位置，初始值为 0。
• result 是一个列表，用于存放模式串在主串中所有匹配的起始索引。

主循环

    for i in range(n):

• 借助 for 循环对主串的每个字符进行遍历，i 是主串当前正在匹配的位置。

匹配失败时的回退操作

        # 当j>0且当前字符不匹配时，j回退到next[j-1]
        while j > 0 and main_str[i] != pattern[j]:
            j = next_array[j-1]

• 当 j 大于 0 并且主串当前字符 main_str[i] 和模式串当前字符 pattern[j] 不匹配时，就需要将模式串的指针 j 回退到 next[j - 1] 所指示的位置。
• 这样做的目的是利用 next 数组中存储的最长相等前后缀信息，避免主串指针 i 回溯，从而提升匹配效率。

匹配成功时的操作

        # 如果当前字符匹配，j和i同时后移
        if main_str[i] == pattern[j]:
            j += 1

• 要是主串当前字符 main_str[i] 和模式串当前字符 pattern[j] 匹配，就把模式串的指针 j 向后移动一位，继续匹配下一个字符。

模式串完全匹配时的操作

        # 如果模式串完全匹配（j等于模式串长度）
        if j == m:
            result.append(i - m + 1)  # 记录匹配的起始位置（i是模式串末尾，起始位置是i-m+1）
            j = next_array[j-1]  # 回退j，继续查找下一个可能的匹配

• 当 j 等于模式串的长度 m 时，意味着模式串已经在主串中完全匹配。
• i - m + 1 就是模式串在主串中的起始位置，将其添加到 result 列表里。
• 接着把模式串的指针 j 回退到 next[j - 1] 所指示的位置，继续在主串中查找下一个可能的匹配。

返回结果

    return result

• 最后返回 result 列表，该列表包含了模式串在主串中所有匹配的起始索引。
  综上所述，kmp_search 函数借助 next 数组，避免了主串指针的回溯，能够高效地在主串中查找模式串的所有起始位置。

下面结合具体的字符串实例，为你详细推演 kmp_search 函数中这部分代码的计算过程。假设主串 main_str = "ABABABCABAB"，模式串 pattern = "ABABC"，next 数组为 [0, 0, 1, 2, 0]。

核心部分代码逻辑推导

# 当j>0且当前字符不匹配时，j回退到next[j-1]
while j > 0 and main_str[i] != pattern[j]:
    j = next_array[j-1]

这段代码的核心逻辑是：在主串和模式串匹配过程中，若当前字符不匹配且 j 大于 0，就将 j 回退到 next[j - 1] 所指示的位置。

计算推演过程

初始状态

• i 是主串的当前匹配位置，初始为 0。
• j 是模式串的当前匹配位置，初始为 0。
• next 数组为 [0, 0, 1, 2, 0]。

匹配过程

1. i = 0，j = 0

   • main_str[0] = 'A'，pattern[0] = 'A'，字符匹配，j 变为 1。

2. i = 1，j = 1

   • main_str[1] = 'B'，pattern[1] = 'B'，字符匹配，j 变为 2。

3. i = 2，j = 2

   • main_str[2] = 'A'，pattern[2] = 'A'，字符匹配，j 变为 3。

4. i = 3，j = 3

   • main_str[3] = 'B'，pattern[3] = 'B'，字符匹配，j 变为 4。

5. i = 4，j = 4

   • main_str[4] = 'A'，pattern[4] = 'C'，字符不匹配，进入 while 循环：

     • 此时 j = 4 大于 0，main_str[4] 不等于 pattern[4]，执行 j = next_array[j - 1]，即 j = next_array[3] = 2。
     • 再次判断 while 条件，main_str[4] = 'A'，pattern[2] = 'A'，字符匹配，退出 while 循环，j 变为 3。

6. i = 5，j = 3

   • main_str[5] = 'B'，pattern[3] = 'B'，字符匹配，j 变为 4。

7. i = 6，j = 4

   • main_str[6] = 'C'，pattern[4] = 'C'，字符匹配，j 变为 5。此时 j 等于模式串长度 5，说明模式串完全匹配，记录匹配起始位置 i - m + 1 = 6 - 5 + 1 = 2，并将 j 回退到 next_array[j - 1] = next_array[4] = 0，继续查找下一个可能的匹配。

后续匹配过程

继续按照上述逻辑，i 从 7 开始继续遍历主串，重复匹配和回退操作，直到遍历完整个主串。

总结

通过这个推演过程，你可以看到 while 循环在匹配失败时，利用 next 数组将模式串的指针 j 回退到合适的位置，避免了主串指针 i 的回溯，从而提高了匹配效率。在整个匹配过程中，主串指针 i 始终是单调递增的，而模式串指针 j 会根据匹配情况进行动态调整。