KMP#

什么是KMP算法#

在传统字符串匹配算法中，我们总是使用暴力，不断从被匹配字符串中截取子串，将其与模式串进行匹配。但是这样做的时间复杂度比较高为 $O(m\times n)$ ，他会对每一个子串都进行遍历，在这个过程中，模式串往往会被遍历很多次。并且我们注意到：

虽然一个子串与模式串不匹配，但是已经遍历过的部分和模式串是相同的。

所以我们能否根据这个信息将模式串进行特殊处理，减少其遍历次数呢？

这正是KMP算法的核心解决思路。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。

核心思想#

在每次不匹配字符时，我们可以知道子串与模式串前几个字符是一样的，因此可以使用这个信息对模式串处理，记录每个位置的回退信息，也就是最长公共前后缀数组。

主逻辑#

先看算法的主逻辑python实现如下：

1
def kmp_search(m: str, p: str):
2
    next = get_next(p) # 获取next数组
3
    i = j = 0
4
    while i < len(m):
5
        if m[i] != p[j]: # 子串和模式串不匹配
6
            if j:
7
              j = next[j - 1]
8
            else:
9
                # 模式串指针回退至0仍然不匹配，说明当前子串和模式串第一个字符都不匹配。
10
                # 直接移动文本串指针到下一个子串开始位置
11
                i += 1
12
        else:       # 相匹配则继续
13
            i += 1
14
            j += 1
15
         if j == len(p):
16
            return i - j
17
      return -1

很显然，算法的主逻辑和暴力解差距不是很大，但存在着关键区别：

kmp算法的文本串指针不会回退，由next数组在已遍历过的字符中寻找可用最长前缀，指针i只需要判断当前字符和模式串的指针j字符是否相同

最长公共前后缀#

首先明确什么是前缀和后缀：

前缀指从开头连续截取的子串，但不包含整个串本身。
后缀指从结尾连续截取的子串，但不包含整个串本身。

接下来就最核心的部分，next数组是什么？如何求next数组？

先看这样一个例子：

Note

模式串(pattern)：

ababc

文本串(text)：

abababc

当i=4&&j=4时，模式串字符为c而文本串字符为a，如果采用暴力匹配的方式我们会将j回退为0，i回退为1，然后重新开始匹配。

但是我们显然可以发现将i回退至1后重新匹配效率太差了，而将j回退至2却可以非常完美地契合前缀ab，这时比较pattern[2]处的字符就可以了，也就是i完全不需要回退，这就提高了效率。

那么如何让计算机像人一样能够得到最优的回退值呢？

重新思考一下我们观察的过程：

在i=4&&j=4时字符不匹配，期望获得j的回退值
可以看见已经匹配过的部分为abab，前缀ab和后缀ab是完全相等的，最长前后缀为2
联想到保留长度为2的公共前后缀，因此下一次从 pattern[2] 继续比较就可以完美匹配从索引2开始的子串ababc

不难发现我们利用了已经匹配过的字符串前后缀的关系。即匹配成功的子串abab的前缀有：a、ab、aba，后缀有b、ab、bab。子串后缀有与前缀完全相同的子串ab，而中间的其他字符完全不匹配，因此可以直接将模式串移动至与后缀ab对齐。

1
文本串:    a b a b a b c
2
模式串:    a b a b c
3
                  ↑ mismatch
4

5
已匹配:
6
a b a b
7

8
最长公共前后缀:
9
a b
10

11
移动后:
12

13
文本串:    a b a b a b c
14
模式串:        a b a b c

Important

对上面的逻辑进行总结：

当匹配子串和模式串不相同时，通过寻找已匹配字符串的最大公共前后缀确定模式串指针的回退值，进而优化整个匹配过程

现在问题变成了寻找最大公共前后缀。

仍然先看例子，模式串为 $ababc$ 时:

a：无前后缀，将其回退值设置为0
ab：前缀:a，后缀：b。没有重复前后缀，回退值设置为0
aba：前缀:a、ab，后缀a、ba。有最大公共前后缀a，回退值设置为1
abab：前缀:a、ab、aba，后缀b、ab、bab。有最大公共前后缀ab，回退值设置为2
ababc：前缀:a、ab、aba、abab，后缀c、bc、abc、babc。没有最大公共前后缀，回退值设为0

next数组为[0,0,1,2,0]

我们编写一个简易的程序模拟一下这个过程：

1
def get_next(pattern: str) -> list:
2
    next=[0] * len(pattern)
3
    for i in range(1, len(pattern)): # 由于仅一个字符无前后缀，因此从第二个字符开始
4
        for j in range(1, i+ 1):     # 枚举从j至i的子串
5
            flag = True
6
            for x in range(j, i + 1):
7
                if pattern[x] != pattern[x - j]: # 存在字符未匹配成功，不满足前后缀的要求
8
                    flag = False
9
                    break
10
            if flag:                        # 匹配成功，更新最大前后缀
11
                next[i] = max(next[i], i - j + 1)
12
                break       # 从最大一一枚举的方式只要找到就必是最大前后缀
13
    return next

发现问题了吗，当出现不匹配的字符时这个程序会整体回退，时间复杂度很高为 $O(m^3)$ 。

分析一下这个算法：

首字符不匹配时抛弃该子串，进入下一个子串的匹配，指针 $j+1$
已经匹配了部分字符，但出现了未匹配字符进入下一个子串匹配，指针 $j+1$
完全匹配，跳出内循环，指针 $i+1$

很显然情况1和情况3是无法继续优化的，因为这是字符串匹配不能跳过的步骤，只能针对情况2进行优化。

注意到情况2中已经有部分匹配的字符了，后面的子串长度必然更小，且后续成功匹配的前后缀串必然位于已经成功匹配的串中，所以新的公共前后缀只能在这个已匹配区域内部继续寻找。就像下面的例子一样：

模式串：abcabdddabcabc

假设已经进行至前缀：abcabd，后缀：abcabc，最后一个字符不相同，但是前面的部分abcab是完全相同的，继续寻找下去，若存在完全匹配的前后缀，他必然位于abcab中，因为这是整个字符串的前缀，不可改变。

进一步说，继续缩小的前缀必然完全位于abcab中，且仅顺序截取字符，而后缀除去不匹配的字符，剩余的串也必然位于abcab中（因为这是模式串中除去最后一个字符的后缀，因为继续缩小，剩余的串长度必然缩小），也就是说我们只需要寻找串abcab的最长前后缀就可以找到j回退的最优值是多少，确保前缀和后缀已经有部分相等了，接下来只需要专注于未匹配成功的即可。如本例中，j回退至j-2即可，比较前缀abc和后缀abc，完全相同，找到最大前后缀。

但是我们注意到abcab既然是整个串的前缀，在顺序求next数组的过程中我们已经求过他的最长前后缀了，这是个可以直接利用的信息。按照这个思路上面的代码可以优化为如下代码：

1
def get_next(pattern: str) -> list:
2
    next = [0] * len(pattern)
3
    i, j= 1, 0
4
    while i < len(pattern):
5
        while j and pattern[i] != pattern[j]:
6
            j = next[j - 1]    # 不匹配进行回退，找到已经匹配部分的最长公共前后缀
7
        if pattern[i] == pattern[j]:  # 匹配则将指针右移一位
8
            j += 1
9
        next[i] = j
10
        i += 1
11

12
    return next

虽然代码中有两层循环，但内层循环中变量 j 每次都会减小，而 j 总共增加不超过 m 次，因此所有内层循环的总执行次数也是 O(m)，即时间复杂度为 $O(m)$ .

最终版的kmp算法如下：

1
def get_next(pattern: str) -> list:
2
  n = len(pattern)
3
  next = [0] * n
4
  i, j = 1, 0
5
  while i < n:
6
    if j and pattern[i] != pattern[j]:
7
      j = next[j - 1]
8
    else:
9
      if pattern[i] == pattern[j]:
10
        j += 1
11
      next[i] = j
12
      i += 1
13
  return next
14

15

16
def kmp_search(text: str, pattern: str) -> int:
17
  next = get_next(pattern)
18
  i = j = 0
19
  while i < len(text):
20
    if text[i] != pattern[j]:
21
      if j:
22
        j = next[j - 1]
23
      else:
24
        i += 1
25
    else:
26
      j += 1
27
      i += 1
28
    if j >= len(pattern):
29
      return i - j
30
  return -1

时间复杂度为 $O(m + n)$ ，其中m为模式串的长度，n为文本串的长度。

进一步优化#

当模式串(pattern)有很多重复字符时如：aaab，我们得到的next数组为[0, 1, 2, 3, 0]。现在考虑这样的一个匹配串(text)：aacaaab。

令模式串的指针为j，匹配串的指针为i。

当i=2 && j=2时，显然pattern[2]=‘a’ 不等于 text[2]=‘c’，因此指针j进行回退，查next数组可知：j=next[j - 1]= 1，因此j回退至1。但是很明显pattern[1]!=text[2]，需要继续回退并且最终回退至0。

从中可以发现，连续相同字符回退值是以第一个出现的位置为基准的，因为当出现不匹配时可以断定前面已匹配成功的相同字符与模式串的当前字符必然不同，如上例所示”b” 必不可能与前面已经匹配成功的”aa”中字符相同。

因此在生成求next数组时可以考虑这种情况，将连续相同字符的全部置为第一个字符出现的next值。

1
def get_nextval(pattern: str) -> list:
2
    n = len(pattern)
3
    nextval = [0] * n
4
    i, j = 1, 0
5

6
    while i < n:
7
        if j == 0 or pattern[i] == pattern[j]:
8
            i += 1
9
            j += 1
10
            if i < n:       # 防止越界，因为 nextval 长度只有 n
11
                if pattern[i] != pattern[j]:
12
                    nextval[i] = j
13
                else:
14
                    nextval[i] = nextval[j]
15
        else:
16
            j = nextval[j]  # 不匹配时回退
17

18
    return nextval

F&Q#

你也许发现了，为什么我们求的的next数组和严蔚敏老师的数据结构教材上的不一样？

Note

严版kmp算法实现：

1
void getNext(SString T, int next[]){
2
    int i = 1, j = 0;
3
    next[1] = 0;
4
    while(i < T.length){
5
        if(j == 0 || T.ch[i] == T.ch[j]){
6
            next[++i] = ++j;
7
        }else{
8
            j = next[j];
9
        }
10
    }
11
}
12

13
int indexKMP(SString S, SString T, int next[]){
14
    int i = 1, j = 1;
15
    while(i <= S.length && j <= T.length){
16
        if(j == 0 || S.ch[i] == T.ch[j]){
17
            i++;
18
            j++;
19
        }else{
20
            j = next[j];
21
        }
22
    }
23
    if(j > T.length)
24
        return i - T.length;
25
    else
26
        return 0;
27
}

解释如下：

首先严老师的教材上next数组索引是从1开始的，而在本文（最普遍的kmp实现）中一般从索引0开始
把本文的 next 数组（即部分匹配表 PMT）整体右移一位，首位补 -1，然后所有元素 +1，就得到了严蔚敏教材中 1‑based 的 next 数组。例如 [0,0,1,2,0] → 右移补 -1 得到 [-1,0,0,1,2] → 全部 +1 得到 [0,1,1,2,3]，与严版一致。

准确来说，严版的是模式串指针j与文本串指针i不匹配时，指针j的应该回退的位置，即j=next[j]，失配后模式串下一步应该比较的位置。

在此文的版本中，由于索引从0开始，next数组存储的是最长前后缀的长度，这天然地表示了指针j应该回退的位置，但是由于是当前字符不匹配，所以需要回退的值是已经匹配成功的字符串的最长前后缀值，即j=next[j-1]，最长前后缀长度。

Important

严版和本文均是kmp算法的正确实现，不同在于严版为了方便回退将最长前后缀整体右移一个单位再整体加一，并且索引从1开始；在本文中索引从0开始，因此天然满足指针回退到的位置为最长公共前后缀的前缀最后一个字符结束的位置+1，故而不需要整体加一，并且由于没有整体右移，因此回退值为next[j-1]

我与我周旋久，宁作我

KMP算法教程

KMP#

什么是KMP算法#

核心思想#

主逻辑#

最长公共前后缀#

进一步优化#

F&Q#

文章分享

目录