KMP算法

KMP是求解字符串模式匹配的经典算法。

字符串模式匹配问题：给定字符串pattern(模式)，和字符串text，找出所有pattern在text中出现的位置。为了方便，下面的讲述中会用到python语言。

KMP算法思想

我们从最简单的字符串匹配算法开始，一步步推导出KMP算法的思想。

对于字符串匹配，容易想到以下算法：

pos, i = 0, 0
while pos + len(pattern) < len(text):
  while True:
    # 进行到pattern末尾，找到一个匹配
    if i >= len(pattern):
      print pos
      break
    if pattern[i] == text[pos + i]:
      i += 1
    else:
      # 发现不同字符，当前位置不能匹配
      break

  i, pos = 0, pos+1

KMP算法源自于以下考虑：当上述程序运行到最后一行时，能否将pos多增加几位，i能否不从0开始？

例1：如下图所示，发现pattern[3] != text[pos + 3]时，break出内层循环，然后i = 0，pos += 1。

观察发现，pattern[0:3]的三个字符("ABC")两两不同，容易判断出，位置pos+1和pos+2，必然不匹配，所以可以省略掉这两个位置的比较，直接令pos += 3。而且，这个特性和text无关，是pattern自己的特点，可以描述如下：当i==3时，如果pattern[i] != text[pos+i]，可以令pos += 3。

例2：如果pattern[0:5]是ABCAB，如下图所示。和之前的情况一样，可以直接跳过pos+1和pos+2，直接令pos += 3。此外，我们还可以发现，i可以直接等于2，而不必从0开始，因为pos += 3之后，pattern的前两个"AB"自动就和text后面两个"AB"对齐了。

上面观察到的两个规律，都是pattern字符串本身固有的，和text无关。因此，我们可以提前将这些特征提取出来，用以加速在任何字符串中查找pattern的过程。

确切地说，我们希望预先计算出：当break时，pos可以增加多少，i可以从多少开始。

我们将pos逐步加1，直到已知的部分完全匹配为止。如下图所示

可以发现，因为pattern[0:5]存在一对相同的前缀和后缀，长度为2，所以当pos增加到3时，后面的两个字符完全重合。这正是例2中的情况。如果不存在这样的后缀，如例1中的情况，pos就可以一直增加到i。

我们用NEXT数组表示这么一个数组：NEXT[k]表示字符串pattern[0:k]包含的最大的相同前后缀的长度，如果不存在相同的前后缀，则NEXT[k] = 0。更新我们的程序如下(注意到只修改了最后一行)

pos, i = 0, 0
while pos + len(pattern) < len(text):
  while True:
    # 进行到pattern末尾，找到一个匹配
    if i >= len(pattern):
      print pos
      break
    if pattern[i] == text[pos + i]:
      i += 1
    else:
      # 发现不同字符，当前位置不能匹配
      break

  i, pos = NEXT[i], pos+(i-NEXT[i])

注：为什么一定是最大的前后缀呢？因为在增大pos的过程中，重合部分逐渐减小。第一次遇到字符完全匹配时，重合的必然是最大的前后缀。

求解NEXT数组

为了求NEXT数组，我们可以把两个pattern字符串对齐，然后将其中一个向右移动，直到重合部分完全匹配，此时重合部分的长度就是我们要求的相同前后缀的长度。这个过程和上一幅图中描述的一样。

不过，假设已经求出了NEXT[0]到NEXT[k]，现在求NEXT[k+1]，我们可以利用已经求出的部分结果加速这个过程。

首先我们有如下发现：NEXT[k+1] <= NEXT[k] + 1。也就是说，随着k增加1，NEXT[k]最多增加1。

证明：根据定义，字符串pattern[0:k+1]中，长度为NEXT[k+1]的前后缀相等。将这一对前后缀各自去掉最后一个字符，前缀仍然是长度为NEXT[k+1]-1的前缀，而后缀变成了pattern[0:k]的长度为NEXT[k+1]-1的后缀。如下图所示。

所以pattern[0:k]至少有一对长度为NEXT[k+1]-1的相同前后缀，因此NEXT[k] >= NEXT[k+1]-1。所以，NEXT[k+1] <= NEXT[k] + 1。

所以，我们得到了一个上界，可以不用从头开始，而是从重合部分长度为NEXT[k] + 1的地方开始。如下图所示。

此时，如果对齐点右边的字符相等，就立刻得到NEXT[k+1]=NEXT[k]+1。如上图所示。

如果不相等，也不必一步一步向右移动。如下图所示，利用已经计算好的NEXT数组，可以继续将下面的字符串往右跳跃：

就像寻找字符串匹配一样，利用已经求出的NEXT数组的部分，继续将下面的字符串往右跳跃。如下图所示

这样一步步跳的过程中，左边始终保持着匹配。而右边那个字符一旦也相同了，就找到了一对相同的前后缀。如果直到左边为空了，右边这个字符仍然不匹配，就意味着要找的相同前后缀不存在，此时返回0。

完整的KMP算法C++实现代码可以参见：https://github.com/yczhangsjtu/Algorithms/blob/master/hihocoder/kmp.cpp