kmp算法示例和推导 最后更新时间：2025年04月29日 ## 算法代码示例 ```python 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 | 子串`pattern[0...i]` | 前缀集合 | 后缀集合 | 最长相等前后缀长度 | next[i] | |-------|-----------------------|----------|----------|---------------------|---------| | 0 | "A" | 无（真前缀为空） | 无（真后缀为空） | 0（无相等前后缀） | 0 | | 1 | "AB" | ["A"] | ["B"] | 0（无相等前后缀） | 0 | | 2 | "ABA" | ["A", "AB"] | ["A", "BA"] | "A"（长度1） | 1 | | 3 | "ABAB" | ["A", "AB", "ABA"] | ["B", "AB", "BAB"] | "AB"（长度2） | 2 | | 4 | "ABABC" | ["A", "AB", "ABA", "ABAB"] | ["C", "BC", "ABC", "BABC"] | 0（无相等前后缀） | 0 | #### 详细解释每个位置的推导： - **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"为例） ```python 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"为例） | 迭代i | pattern[i] | j初始值 | 比较pattern[i]和pattern[j] | 操作 | next_array[i] | |-------|------------|---------|----------------------------|------|---------------| | 1 | B | 0 | B（i=1） vs A（j=0） → 不匹配 | j=0（j不大于0，不进入while循环） | 0（j=0未变化） | | 2 | A | 0 | A（i=2） vs A（j=0） → 匹配 | j=0+1=1 | 1（j=1） | | 3 | B | 1 | B（i=3） vs B（j=1） → 匹配 | j=1+1=2 | 2（j=2） | | 4 | C | 2 | C（i=4） vs A（j=2） → 不匹配 | 进入while循环：j=next[j-1]=next[1]=0 → 再次比较C（i=4） vs A（j=0） → 不匹配 → j=0（退出循环） | 0（j=0） | ### 五、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函数定义与参数 ```python def kmp_search(main_str, pattern, next_array): """使用KMP算法在主串中查找模式串的所有起始位置""" ``` - `kmp_search` 是函数名。 - `main_str` 是主串，也就是要在其中查找模式串的字符串。 - `pattern` 是模式串，即要查找的目标字符串。 - `next_array` 是通过 `compute_next` 函数计算出的模式串的 `next` 数组，其用途是在匹配失败时指导模式串指针的回退。 ### 初始化变量 ```python n = len(main_str) m = len(pattern) j = 0 # 模式串的当前匹配位置 result = [] # 保存所有匹配的起始索引 ``` - `n` 代表主串的长度。 - `m` 代表模式串的长度。 - `j` 表示模式串当前正在匹配的位置，初始值为 0。 - `result` 是一个列表，用于存放模式串在主串中所有匹配的起始索引。 ### 主循环 ```python for i in range(n): ``` - 借助 `for` 循环对主串的每个字符进行遍历，`i` 是主串当前正在匹配的位置。 ### 匹配失败时的回退操作 ```python # 当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` 回溯，从而提升匹配效率。 ### 匹配成功时的操作 ```python # 如果当前字符匹配，j和i同时后移 if main_str[i] == pattern[j]: j += 1 ``` - 要是主串当前字符 `main_str[i]` 和模式串当前字符 `pattern[j]` 匹配，就把模式串的指针 `j` 向后移动一位，继续匹配下一个字符。 ### 模式串完全匹配时的操作 ```python # 如果模式串完全匹配（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]` 所指示的位置，继续在主串中查找下一个可能的匹配。 ### 返回结果 ```python return result ``` - 最后返回 `result` 列表，该列表包含了模式串在主串中所有匹配的起始索引。 综上所述，`kmp_search` 函数借助 `next` 数组，避免了主串指针的回溯，能够高效地在主串中查找模式串的所有起始位置。 下面结合具体的字符串实例，为你详细推演 `kmp_search` 函数中这部分代码的计算过程。假设主串 `main_str = "ABABABCABAB"`，模式串 `pattern = "ABABC"`，`next` 数组为 `[0, 0, 1, 2, 0]`。 ### 核心部分代码逻辑推导 ```python # 当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` 会根据匹配情况进行动态调整。
Comments | NOTHING