KMP算法实现及改良

与每趟匹配失败都从头开始重新比较的暴力匹配算法不同，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 = 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 数组呢？

• 已知 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 数组

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 算法

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;  
} 

第三步：测试

#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 需要依次回退到 2、1、0，我们可以改善 next 数组，让 j 直接回退到 0 位置，减少无效判断次数。

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

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

代码如下：

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

五、参考

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