KMP算法

发表于 更新于 分类于 阅读次数：
字符串模式匹配算法解析

本部分如果想要视频解析，推荐看天勤的解析【天勤考研】KMP算法易懂版，本人也是看了天勤的解析才写下本文

KMP算法用于快速比较两个字符串，从主串中匹配一个给定的模式串，KMP算法解决了简单暴力算法中模式串指针的需要来回移动的问题，执行起来效率更高

提示

本文中所有代码均默认串从1位置开始

简单暴力算法

为什么这么说呢，先来看一个暴力算法的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef struct {
	char *ch;
	int length;
} Str;

int index(Str s, Str subs) {
	// 定义三个指针，i j指向主串和模式串，k指向上一次主串中不相等的位置
	// 这里假设字符串都是从1位置开始
    int i = 1, j = 1, k = 1;
    while(i <= s.length && j <= subs.length) {
	    // 如果当前指针所指位置相等，指针后移一位
	    if (str.ch[i] == subs.ch[i]) {
		    i++;
		    j++;
	    } else {
		    // 匹配失败，模式串相对主串后移一位
		    i = ++k;
		    // 再次从模式串初始位置开始遍历
		    j = 1;
	    }
    }
    if(j > subs.length) return k;  // 匹配成功，返回模式串在主串中的位置
    return 0; // 否则返回失败标记
 }

假设我们需要从串 “ABAABABBABAAABA” 中找到 ABBABA 所在的位置

简单暴力算法中，我们让主串和模式串分别从1位置开始遍历，当遍历到 s.ch[3] 和 subs.ch[3]时，发生不匹配，此时会让模式串相对主串后移一位，重新开始遍历

而很明显，将模式串后移一位后，s.ch[2] != subs.ch[1]，此时仍然需要将模式串后移一位，如下图

在某一次循环后，当 s.ch[6] != subs.ch[3] 时，需要再次后移模式串，会将模式串指针 j 重新指向1

很明显后移一次会使得 s.ch[5] != subs.ch[1] ，需要再次移动模式串

最终成功匹配到字串，此时指针 j 已经指向模式串末尾，根据上面的代码，会将指针 j++ 变成 7，使得 j > subs.length，不满足循环条件跳出循环，并返回主串中匹配成功的位置 6

KMP算法

kmp算法实际上是一个动态规划问题，求next数组实际上就是动态规划过程中的dp数组，下面是解析

算法分析

从上面的过程可以看到，在移动字串的过程中始终有如下这种 主串与模式串头位置就匹配失败

或者 主串与模式串已经比较过的部分匹配失败

如这里已经比较过主串的 1 2 3 4 5位置与模式串 1 2 3 4 5位置相同

但是在移动模式串时，只将模式串移动了一位

能不能跳过中间这些直接就失败的状态呢？这就是KMP算法会解决的问题

还是以这个为例

KMP算法会直接进行如下的过程，并从主串的 6 位置与模式串的 3 位置开始比较

这个过程是怎么来的呢？

首先 KMP 算法会找到模式串发生不匹配位置（上面的6位置）以前的 最长公共子串，如下图

并直接将前面一个字串移动到后面一个字串的位置

而在计算机中其实不能实现将模式串后移这种操作，所以通过代码实现就是将 i 指针不动，j 指针移动到 最长公共子串+1 的位置(比如上面就是3位置)，让 s.ch[i] 和 subs.ch[j] 继续比较，从而跳过了很多重复的失败过程，同时避免了 j 指针的来回移动

而在字串中每个位置都可能发生不匹配，每个位置都可以向前找到最长公共子串，且和模式串位置一一对应，因此我们也可以用一个数组来存储下一步主串和模式串需要比较的位置，因此求得的这个数组就被称作下一步数组，也叫 next 数组

根据上面的描述，KMP算法匹配模式串的步骤就分解成了三步

Tip

  1. 求每个位置之前的最长公共字串长度
  2. 求解next数组
  3. 遍历主串与模式串，发生不匹配时执行 j=next[j]，继续遍历

求解Next数组

从上面可以看到，求解next数组最重要的一步是求最长公共子串，或者叫最长公共前后缀
上面这个例子中，模式串总长度比较短，可以在很快的求得每个位置的最长公共子串如下所示

数组下标 0 1 2 3 4 5 6
模式串 A B B A B A
next 0 1 1 1 2 3

其中会出现一些特殊情况，比如1 2 3位置，这几个位置是没有公共前后缀的，所以对这个过程做出一些规定

特殊情况

  1. next 数组第 1 位置直接赋值为 0 ，表示直接将模式串后移一位 (或指向主串的指针后移)
  2. 没有公共前缀的地方赋值为1

但是假如模式串很长，直接求解最长子串的过程其实就跟简单暴力算法没什么区别了，所以这一个过程也可以进行优化

以下面的模式串为例，我们已经求得了6位置的next值3，现在要求7位置的next值，怎么办呢？

数组下标 0 1 2 3 4 5 6 7 8 9 10
模式串 A B B A B A B B A B
next 0 1 1 1 2 3

这里为了更直观表示此过程，将模式串复制一份，再按照下面的方式对其两个串，这是不是又回到了上面的求解主串与模式串的匹配与否问题呢

而在这个例子中，已经求得了 next[6] = 3 ，而这个值表示的是 6 位置之前的最长公共子串的长度+1，现在要得到 7 位置的最长公共子串

假如 subs.ch[6] == subs.ch[3]，说明子串中1~3位置和4~6位置相等，即这部分是最长公共前后缀，直接让next[7] = next[6] + 1 即可

假如不相等，那么就回到了主串与模式串匹配问题中，发生不匹配时子串的指针应该跳到哪里的问题，上面这里就是在子串 3 位置发生不匹配，next[3] 已知，而 subs.ch[next[3]] == subs.ch[7] 所以 next[7] = next[3] = 1

接下来由特殊推广为一般情况

假如需要求解 next[j] 的值，而 next[j-1] = t，只需要比较 subs.ch[t] 与 subs.ch[j-1] 是否相等
若相等，next[j] = next[j-1] + 1
否则，t = next[t] ，再执行一次判断，直到匹配或t == 0为止

C++代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
void getnext(Str subs, int next[]) {
	// j指针指向字符串
	int t = 0, j = 1;
	next[1] = 0; // 对应特殊情况 1，规定首位为 0
	while(j<subs.length) {
		if (t == 0 || subs.ch[t] == subs.ch[j]){
			next[++j] = ++t; // 等同于 t++; j++; next[j]=t;
		} else {
			t = next[t];
		}
	}
}

KMP代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int kmp(Str s, Str subs,int next[]) {  
    int j = 1;  
    int i = 1;  
    while (i<=s.length&&j<=subs.length) {  
        if (j == 0 || s.ch[i] == subs.ch[j]) {  
            i++;  
            j++;  
        } else {  
            j = next[j];  
        }  
    }  
    if (j > subs.length)  
        return i-subs.length;  
    return 0;  
}

完整的kmp demo代码可见 kmp.cpp · lm379/datastr - 码云 - 开源中国