字符串匹配之 KMP

algorithm

Knuth-Morris-Pratt 字符串查找算法，简称为“KMP算法”，此算法可在一个主“文本字符串”S内查找一个“词”W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。（来自Wiki的简要解释）

“部分匹配”表

从上面解释中最重要的就是如何确定下一个匹配将在哪里开始。这里KMP使用了一个“部分匹配”表，当失配时将通过这个表来确定下一个匹配将在哪里开始，因为可以用数组来表示，我们又称其为 next 数组。那么这个 next 数组到底长什么样子又是怎么算出来的呢。

next 数组的构成是这样的，它的下标对应于目标字符串 P 的每个字符的位置，它的 value 就是当失配时下一个匹配将在何处开始的数值，也就是说当 P 的第 j 的字符匹配失败时，下一次将从字符串 P 的 next[j] 处开始匹配。下面举个例子来说明：

现有目标字符串 P = 'abdabch'，经计算其对应的 next 数组就是 [-1, 0, 0, 0, 1, 2, 0]。（下面会详细介绍 next 数组的计算方式）
现在先来看下 next 数组的使用方式：
假设现有主字符串 S = 'cdabdabpoabvb'
1. 依次匹配，当匹配到第6位时，也就是 S[7] != P[5]
2. 查找 next 数组，next[5] = 2
3. 保持 S 的指针不变，移动 P 的指针到 P[next[5]] 也就是 P[2] 位置继续匹配
4. 重复

下面再来说说 next 数组本身，还是借助上面例子来说明：
1. 假设指向 S, P 的指针分别为 i, j
2. 那么当 j = 5, i = 7 时，S[7] != P[5] ，P[5] 前面的字符 'abdab' 与 S 已完成匹配
3. 那么假如 'abdab' 首部尾部有重复字符串，如现在就有重复前后缀 ab ，那么当匹配失败时，可以知道后缀一定是匹配成功的，那么与后缀匹配的前缀也一定匹配成功，那么下一次的匹配就可以从之后的一位开始（在此处也就是 p[2] 处）。

那么至此问题就转化为了求给定字符串的最长匹配的前缀后缀的问题。

先看构建 next 数组的代码

k = -1
j = 0
next_arr = Array.new(p_length, 0)
next_arr[0] = -1
while j < p_length
  # when string_p[k] == string_p[j], then next_arr[j+1] = k + 1
  if k == -1 || string_p[k] == string_p[j]
    k += 1
    j += 1
    next_arr[j] = k
  else
    # 往前查找较短的匹配项
    k = next_arr[k]
  end
end
next_arr

利用 next 数组进行位置查找的代码：

class StringKmp
  def initialize
    @string_a = 'abcddacbabdkllab'
    @string_p = 'abd'
    @a_length = @string_a.length
    @p_length = @string_p.length
  end
  def main
    next_arr = build_next
    i = 0
    j = 0
    while i < @a_length && j < @p_length
      if j == -1 || @string_a[i] == @string_p[j]
        j += 1
        i += 1
      else
        j = next_arr[j]
      end
    end
    # matching complete
    if j == @p_length
      i - j
    else
      -1
    end
  end
  def build_next
    k = -1
    j = 0
    next_arr = Array.new(@p_length, 0)
    next_arr[0] = -1
    while j < @p_length
      # when string_p[k] == string_p[j], then next_arr[j+1] = k + 1
      if k == -1 || @string_p[k] == @string_p[j]
        k += 1
        j += 1
        next_arr[j] = k
      else
        # 往前查找较短的匹配项
        k = next_arr[k]
      end
    end
    next_arr
  end
end

模式串中每个字符之前的前缀和后缀公共部分的最大长度