KMP字符串匹配算法原理与实现
字数 2225 2025-11-18 05:04:19

KMP字符串匹配算法原理与实现

KMP算法是一种高效的字符串匹配算法，由Knuth、Morris和Pratt三位科学家共同提出。它的核心思想是通过预处理模式串（Pattern），构建一个部分匹配表（通常称为next数组），利用匹配失败时的已知信息避免不必要的回溯，将时间复杂度从暴力匹配的O(m*n)优化到O(m+n)。

1. 问题背景与暴力匹配的局限性
字符串匹配问题：给定一个主串S（长度为n）和一个模式串P（长度为m），在S中查找P首次出现的位置。
暴力匹配算法：从S的每个字符开始，逐个与P的字符比较。若某次匹配失败，主串指针回退到本次起始位置的下一个字符，模式串指针回退到开头。最坏情况下需比较m*n次，效率低下。

2. KMP算法的核心思想：利用已匹配信息
当某次匹配失败时，暴力匹配会丢弃本次匹配的所有信息，从头开始。KMP算法观察到：匹配失败时，已匹配的子串是已知的，利用这个信息可以跳过一些绝不会成功的匹配尝试。

  • 示例：S = "ABABABC", P = "ABABC"
    • 第一次匹配：S[0:4] = "ABAB" 与 P[0:4] = "ABAB" 匹配，但S[4] = 'A' 与 P[4] = 'C' 失败。
    • 暴力匹配：主串指针回退到S[1]，重新从P[0]开始比较。
    • KMP策略：已匹配的"ABAB"中，后缀"AB"（P[2:4]）与前缀"AB"（P[0:2]）相同。直接将P右移2位，使P[0:2]对齐S[2:4]，继续从S[4]和P[2]开始比较，避免回溯。

3. 部分匹配表（next数组）的构建
next数组定义：对于模式串P，next[i]表示子串P[0:i]（长度为i+1）中，最长的相等真前缀和真后缀的长度（真前缀/后缀指不包含自身）。

  • 计算步骤（递推法，i从0到m-1，j表示当前匹配的前缀长度）：
    1. next[0] = -1（初始条件，无真前缀/后缀）
    2. 设j = -1, i = 0
    3. 循环 while i < m-1:
      • 若 j == -1 或 P[i] == P[j]：
        • i++, j++
        • next[i] = j（P[i]前的最长相等前后缀长度为j）
      • 否则：
        • j = next[j]（失配时，j回退到前一个匹配位置）
  • 示例：P = "ABABC"
    • i=0, j=-1 → j=-1 → i=1, j=0, next[1]=0
    • i=1, j=0 → P[1]='B' != P[0]='A' → j=next[0]=-1
    • i=1, j=-1 → j=-1 → i=2, j=0, next[2]=0
    • i=2, j=0 → P[2]='A' == P[0]='A' → i=3, j=1, next[3]=1
    • i=3, j=1 → P[3]='B' == P[1]='B' → i=4, j=2, next[4]=2
    • 最终next = [-1, 0, 0, 1, 2]

4. KMP匹配过程

  1. 初始化：主串指针i=0，模式串指针j=0
  2. 循环 while i < n 且 j < m:
    • 若 j == -1 或 S[i] == P[j]：
      • i++, j++（字符匹配，双指针后移）
    • 否则：
      • j = next[j]（失配时，j回退到next[j]位置，i不变）
  3. 匹配结果：
    • 若 j == m：返回 i - j（匹配成功）
    • 否则：返回 -1（匹配失败）

5. 完整示例演示
S = "ABABABC", P = "ABABC", next = [-1,0,0,1,2]

  • i=0, j=0: S[0]='A'=P[0] → i=1, j=1
  • i=1, j=1: S[1]='B'=P[1] → i=2, j=2
  • i=2, j=2: S[2]='A'=P[2] → i=3, j=3
  • i=3, j=3: S[3]='B'=P[3] → i=4, j=4
  • i=4, j=4: S[4]='A'≠P[4]='C' → j=next[4]=2
  • i=4, j=2: S[4]='A'=P[2]='A' → i=5, j=3
  • i=5, j=3: S[5]='B'=P[3]='B' → i=6, j=4
  • i=6, j=4: S[6]='C'=P[4]='C' → i=7, j=5
  • j=5=m → 匹配成功，返回i-j=2

6. 算法优化（nextval数组）
若P[j] == P[next[j]]，则下次匹配必然失败。可优化next数组为nextval：

  • 计算nextval[i]：
    • 若P[i] == P[next[i]]，则nextval[i] = nextval[next[i]]
    • 否则nextval[i] = next[i]
  • 示例：P="ABABC", next=[-1,0,0,1,2] → nextval=[-1,0,0,0,2]（避免重复比较）

7. 复杂度分析

  • 时间复杂度：O(m+n)（预处理next数组O(m)，匹配过程O(n)）
  • 空间复杂度：O(m)（存储next数组）

通过以上步骤，KMP算法利用部分匹配表避免了主串指针的回溯，显著提升了匹配效率，尤其适用于模式串重复度高或主串庞大的场景。

KMP字符串匹配算法原理与实现 KMP算法是一种高效的字符串匹配算法，由Knuth、Morris和Pratt三位科学家共同提出。它的核心思想是通过预处理模式串（Pattern），构建一个部分匹配表（通常称为next数组），利用匹配失败时的已知信息避免不必要的回溯，将时间复杂度从暴力匹配的O(m* n)优化到O(m+n)。 1. 问题背景与暴力匹配的局限性 字符串匹配问题：给定一个主串S（长度为n）和一个模式串P（长度为m），在S中查找P首次出现的位置。 暴力匹配算法：从S的每个字符开始，逐个与P的字符比较。若某次匹配失败，主串指针回退到本次起始位置的下一个字符，模式串指针回退到开头。最坏情况下需比较m* n次，效率低下。 2. KMP算法的核心思想：利用已匹配信息 当某次匹配失败时，暴力匹配会丢弃本次匹配的所有信息，从头开始。KMP算法观察到：匹配失败时，已匹配的子串是已知的，利用这个信息可以跳过一些绝不会成功的匹配尝试。 示例：S = "ABABABC", P = "ABABC" 第一次匹配：S[ 0:4] = "ABAB" 与 P[ 0:4] = "ABAB" 匹配，但S[ 4] = 'A' 与 P[ 4 ] = 'C' 失败。 暴力匹配：主串指针回退到S[ 1]，重新从P[ 0 ]开始比较。 KMP策略：已匹配的"ABAB"中，后缀"AB"（P[ 2:4]）与前缀"AB"（P[ 0:2]）相同。直接将P右移2位，使P[ 0:2]对齐S[ 2:4]，继续从S[ 4]和P[ 2 ]开始比较，避免回溯。 3. 部分匹配表（next数组）的构建 next数组定义：对于模式串P，next[ i]表示子串P[ 0:i ]（长度为i+1）中，最长的相等真前缀和真后缀的长度（真前缀/后缀指不包含自身）。 计算步骤（递推法，i从0到m-1，j表示当前匹配的前缀长度）： next[ 0 ] = -1（初始条件，无真前缀/后缀） 设j = -1, i = 0 循环 while i < m-1: 若 j == -1 或 P[ i] == P[ j ]： i++, j++ next[ i] = j（P[ i ]前的最长相等前后缀长度为j） 否则： j = next[ j ]（失配时，j回退到前一个匹配位置） 示例：P = "ABABC" i=0, j=-1 → j=-1 → i=1, j=0, next[ 1 ]=0 i=1, j=0 → P[ 1]='B' != P[ 0]='A' → j=next[ 0 ]=-1 i=1, j=-1 → j=-1 → i=2, j=0, next[ 2 ]=0 i=2, j=0 → P[ 2]='A' == P[ 0]='A' → i=3, j=1, next[ 3 ]=1 i=3, j=1 → P[ 3]='B' == P[ 1]='B' → i=4, j=2, next[ 4 ]=2 最终next = [ -1, 0, 0, 1, 2 ] 4. KMP匹配过程 初始化：主串指针i=0，模式串指针j=0 循环 while i < n 且 j < m: 若 j == -1 或 S[ i] == P[ j ]： i++, j++（字符匹配，双指针后移） 否则： j = next[ j]（失配时，j回退到next[ j ]位置，i不变） 匹配结果： 若 j == m：返回 i - j（匹配成功） 否则：返回 -1（匹配失败） 5. 完整示例演示 S = "ABABABC", P = "ABABC", next = [ -1,0,0,1,2 ] i=0, j=0: S[ 0]='A'=P[ 0 ] → i=1, j=1 i=1, j=1: S[ 1]='B'=P[ 1 ] → i=2, j=2 i=2, j=2: S[ 2]='A'=P[ 2 ] → i=3, j=3 i=3, j=3: S[ 3]='B'=P[ 3 ] → i=4, j=4 i=4, j=4: S[ 4]='A'≠P[ 4]='C' → j=next[ 4 ]=2 i=4, j=2: S[ 4]='A'=P[ 2 ]='A' → i=5, j=3 i=5, j=3: S[ 5]='B'=P[ 3 ]='B' → i=6, j=4 i=6, j=4: S[ 6]='C'=P[ 4 ]='C' → i=7, j=5 j=5=m → 匹配成功，返回i-j=2 6. 算法优化（nextval数组） 若P[ j] == P[ next[ j] ]，则下次匹配必然失败。可优化next数组为nextval： 计算nextval[ i ]： 若P[ i] == P[ next[ i]]，则nextval[ i] = nextval[ next[ i] ] 否则nextval[ i] = next[ i ] 示例：P="ABABC", next=[ -1,0,0,1,2] → nextval=[ -1,0,0,0,2 ]（避免重复比较） 7. 复杂度分析 时间复杂度：O(m+n)（预处理next数组O(m)，匹配过程O(n)） 空间复杂度：O(m)（存储next数组） 通过以上步骤，KMP算法利用部分匹配表避免了主串指针的回溯，显著提升了匹配效率，尤其适用于模式串重复度高或主串庞大的场景。