KMP 算法实现及改良
kecho
  更新于 2022-04-18      6 分钟

与每趟匹配失败都从头开始重新比较的暴力匹配算法不同，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 算法匹配过程中，假设第 j 位失配（从 0 编号）

已知：移动位数 = 已经匹配的字符数（0 ~ j-1 共 j 个） - 最后一个匹配字符的部分匹配值（pm[j-1]）

记为：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 = 0 （next[2] == 0），i = 2 —-> i = 2 （ i 不变）

  2. 第二次匹配（失配时 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 = 1 （next[4] == 1），i = 6 —-> i = 6 （ i 不变）

  3. 第三次匹配（匹配成功 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 数组含义不同，有的是没有右移之前的，有的是右移一位的（如本文），有的是右移一位后数值再加 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;  
            //相当于 j++; next[j]=k+1; 计算出 next[j+1]，然后令 k=next[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 个字符必相同），则 j 需要依次回退到 2、1、0，我们可以改善 next 数组，让 j 直接回退到 0 位置，减少无效判断次数。

用 nextval数组 表示改良后的 next数组，过程如下：

  • 先算出 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

参考

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