KMP算法实现及改良
kecho

与每趟匹配失败都从头开始重新比较的暴力匹配算法不同,KMP算法会按照已记录的数组移动到指定位置开始比较,能大幅提高效率。而该数组记录的内容仅与模式串本身结构相关,与主串无关。

一、理论知识

ababcabcacbab 为主串, i 为主串的遍历指针, abcac 为子串, j 为子串(也称模式串)的遍历指针。pm数组 为对应字符串的部分匹配值(手动计算部分匹配值见附录),next数组pm数组 右移一位得到,其中规定 next[0] = -1

index 0 1 2 3 4
char a b c a c
pm 0 0 0 1 0
next -1 0 0 0 1

在 KMP 算法匹配过程中
已知:移动位数 = 已经匹配的字符数 - 第一个未匹配字符的部分匹配值
记为:move = j - pm[j-1]
替换:move = j - next[j]
j 需要回退到 j - move 位置,即 j = j - move = j - (j - next[j]) = next[j] ,即 j 回退到 next[j] 位置

具体匹配过程:

    1. 第一次匹配(失配时 i = 2, j = 2
      i 0 1 2
      主串 a b a b c a b c a c b a b
      子串 a b c
      j 0 1 2

      子串应向后移动 2 位,j = 2 —-> j = 0next[2] == 0),i = 2 —-> i = 2 ( i 不变)

    1. 第二次匹配(失配时 i = 6, j = 4
      i 0 1 2 3 4 5 6
      主串 a b a b c a b c a c b a b
      子串 # # a b c a c
      j 0 1 2 3 4

      子串应继续向后移动 3 位,j = 4 —-> j = 1next[4] == 1),i = 6 —-> i = 6 ( i 不变)

    1. 第三次匹配(匹配成功 i = 10, j = 5
      i 0 1 2 3 4 5 6 7 8 9 10
      主串 a b a b c a b c a c b a b
      子串 # # * * * a b c a c
      j 0 1 2 3 4 5

      匹配成功,返回子串在主串中的首位置:i - j = 5

所以 KMP 算法如何实现的问题就转化为如何构建 next 数组的问题。

手动如何求 next 数组呢?

  • 法一:先求部分匹配值,再右移得到 next 数组
  • 法二:由 [0…j-1]个字符(已经匹配成功的字符)组成的串的最长相等前后缀长度就是 next[j]

机算如何求 next 数组呢?

  • 已知 next[0] = -1 ,通过 next[j] 来求 next[j+1]
  • 首先判断第 j 个字符是否等于 j 的 next 所指向的字符,相等则 next[j+1] = next[j] + 1
  • 否则继续判断第 j 个字符是否等于 j 的 next 的 next 所指向的字符,直到两者相等或其所指的字符的 next 为 -1 ,然后在所指字符的 next 值基础上加 1 即为 next[j+1]

注:不同书中定义的 next 数组含义不同,有的是没有右移之前的,有的是右移一位的(如本文),有的是右移一位后数值再加 1 的,要具体情况具体分析。另外,本文中数组从 0 开始存字符,有的书可能从 1 开始,对应的代码会有些许差别。

二、代码实现

第一步:求 next 数组

1
2
3
4
5
6
7
8
9
10
11
12
13
void getNextTable(string pattern,int nextTable[]){  
nextTable[0] = -1; //第一个默认为-1
int j=0; //j表示next数组下标
int k=nextTable[j]; //k表示next数组的值
while(j < pattern.size()){ //求next[j+1]
if(k==-1 || pattern[j] == pattern[k]){
nextTable[++j]=++k;
//相当于next[j+1]=k+1; k=next[j+1]; j++;
}else{
k = nextTable[k];
}
}
}

第二步:根据 next 数组编写 KMP 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int KMP(string pattern, string str,int nextTable[]){  
getNextTable(pattern,nextTable);//得到next数组
int i=0; int j=0;
while(i<str.size() && j<pattern.size()){
if(j==-1 || pattern[j]==str[i]){
i++;
j++; //匹配成功则继续匹配
}
else
j = nextTable[j];//匹配失败则回溯
}
if(j==pattern.size())
return i-j; //返回子串在主串的首位置(下标从零开始)
else
return -1;
}

第三步:测试

1
2
3
4
5
6
7
8
9
10
#include <iostream>  
using namespace std;

int main(){
string s="abcac";
string d="ababcabcacbab";
int nextTable[s.size()];
cout<<KMP(s,d,nextTable)<<endl; //匹配成功返回子串在主串的首位置,不匹配返回 -1
return 0;
}

三、改良

假设 j == 3 时失配,而 next[3] == 2, next[2] == 1, next[1] == 0, next[0] == -1 (由计算 next 数组的规则可知,此时模式串中第0、1、2、3个字符必相同),则 j 需要依次回退到 210,我们可以改善 next 数组,让 j 直接回退到 0 位置,减少无效判断次数。

nextval数组 表示改良后的 next数组,求 nextval数组过程

  • 先算出 next 数组(next[0] = -1
  • 如果第 j 个字符和 j 的 next 所指向的字符相同,则它们的 nextval 值相同;否则让 j 的 nextval 值与 next 值相等。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void getNextvalTable(string pattern,int nextvalTable[]){  
nextvalTable[0] = -1; //第一个默认为-1
int j=0; //j表示nextval数组下标
int k=nextvalTable[j]; //k表示nextval数组的值
while(j < pattern.size()){ //求nextval[j+1]
if(k==-1 || pattern[j] == pattern[k]){
if(pattern[++j] == pattern[++k])
nextvalTable[j] = nextvalTable[k];
else
nextvalTable[j] = k; //相当于nextval[j+1]=k+1; k=nextval[j+1]; j++;
}else{
k = nextvalTable[k];
}
}
}

KMP 算法只要将其调用的函数 getNextTable 改为 getNextvalTable ,其余保持不变。

四、附录

求部分匹配值
部分匹配值为字符串的前缀和后缀的最长相等前后缀长度,以 ababa 为例:

  • a 的前缀和后缀都为空集,最长相等前后缀长度为 0
  • ab 的前缀为 { a },后缀为 { b } ,交集为空集,最长相等前后缀长度为 0
  • aba 的前缀为 { a, ab },后缀为 { a, ba },交集为 { a },最长相等前后缀长度为 1
  • abab 的前缀为 { a, ab, aba },后缀为 { b, ab, bab },交集为 { ab },最长相等前后缀长度为 2
  • ababa 的前缀为 { a, ab, aba, abab },后缀为 { a, ba, aba, baba },交集为 { a, aba },最长相等前后缀长度为 3
    所以字符串 ababa 的部分匹配值为 00123

五、参考

《王道数据结构考研复习指导》

  • 本文标题:KMP算法实现及改良
  • 本文作者:kecho
  • 创建时间:2022-04-18 14:41:02
  • 本文链接:https://blog.kecho.top/2022/KMP算法实现及改良.html
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论