KMP 算法

KMP 算法是具有跳跃性的字符串匹配算法。具体请参考百度百科

在本文中,模式串是 Pattern,其长度为 m;待查找字符串是 MainString,其长度是 n。


next 数组

next[ind] 表示子串 Pattern[0 ... ind] 的最长公共前后缀的长度,其中 next[0] = 0。

在计算next数组时,可以根据前一个字符的 next 值,计算后一个字符的 next 值。

kmp-next.jpg

求 next 数组的伪代码如下:

数组 get_next(pattern) {
  next_array = 长为 m 的整型数组,初始时,所有元素都为0;
  for(ind = 1; ind < m; ind++) {
    j = ind;
    while (j > 0) {
      j = next_array[j - 1];
      if (pattern[ind] == pattern[j]) {
        next_array[ind] = j + 1;
        break;
      }
  }

  return next_array;
}

模式匹配

kmp.jpg

图 3 中 MainString[i - j ... i - 1] 和 Pattern[0 ... j - 1] 匹配,但 MainString[i] 和 Pattern[j] 失配,此时,需要回溯

在 KMP 算法中,MainString 无需回溯,Pattern 回溯到 next[j - 1],此即本文开头所讲的跳跃性


Python 实现

tim-chow 的 Github