KMP算法

简介：

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

字符串匹配

有一个主串S = {a,b,c,a,c,a,b,d,c},模式串T = {a,b,d},找出模式串在主串中第一次出现的位置。

之前我们说过BF算法和Rk算法来进行字符串匹配的问题，BF算法是通过最简单的方法，一个一个去遍历比较，RK算法是通过计算散列值来匹配字符串，那KMP又是如何去匹配字符串的呢？

KMP模式匹配算法原理探索

假设主串S= “abcababca”，模式串T= “abcaabx”

用暴风算法去进行匹配时，他会根据主串S[0]和T[0]进行匹配，直到出现不相同的情况，此时会丢弃前面的匹配信息，让S[1]与T[0]相比，直到主串结束或者匹配成功，这样的方式极大的降低了匹配效率。也会增加多余的判断。

15876223054841.png 15876223915482.png

因此，为了减少多余的判断，我们需要用一个数组next，记录模式串中匹配失败时应该回退的位置，而不是匹配失败，又从第一个数开始匹配，这样会产生多余的判断。

KMP模式串匹配算法next数组的推导

一、T = “abcd”

当j = 1时，next[1] = 0
当j = 2时，j由1到j-1范围内只有字符"a"，属于其他情况 next[2] = 1
当j = 3时，j由1到j-1范围内只有字符"ab"，显然a不等于b，属于其他情况 next[3] = 1
当j = 4时，j由1到j-1范围内只有字符"abc"，显然abc不存在相等的情况，属于其他情况 next[4] = 1
因此，next = [0，1，1，1]

二、T = “abcabd”

当j = 1时，next[1] = 0
当j = 2时，j由1到j-1范围内只有字符"a"，属于其他情况 next[2] = 1
当j = 3时，j由1到j-1范围内只有字符"ab"，显然a不等于b，属于其他情况 next[3] = 1
当j = 4时，j由1到j-1范围内只有字符"abc"，显然abc不存在相等的情况，属于其他情况 next[4] = 1
当j = 5时，j由1到j-1范围内只有字符"abca"，显然abca存在相等的字符"a"，因此，可以得到next[5] = 2，表示当第五个位置匹配失败时，直接从模式串的第二个位置与匹配失败的那个字符进行相比。
当j = 6时，j由1到j-1范围内只有字符"abcab"，显然abcab存在相等的字符"ab"，因此，可以得到next[6] = 3，表示当第五个位置匹配失败时，直接从模式串的第三个位置与匹配失败的那个字符进行相比。
因此，next = [0，1，1，1，2，3]

三、T = “aaaabc”
当j = 1时，next[1] = 0
当j = 2时，j由1到j-1范围内只有字符"a"，属于其他情况 next[2] = 1
当j = 3时，j由1到j-1范围内只有字符"aa"，显然存在a等a next[3] = 2
当j = 4时，j由1到j-1范围内只有字符"aaa"，显然前缀aa等于后缀aa，next[4] = 3
当j = 5时，j由1到j-1范围内只有字符"aaaa"，前缀aaa与后缀aaa相等，因此，可以得到next[5] = 4
当j = 6时，j由1到j-1范围内只有字符"aaaab"，前缀与后缀不想等，因此，next[6]= 1

因此，next = [0，1，2，3，4，1]

理解回退

模式串 T = "ababaaaba"

判断前

截屏2020-04-23 下午3.18.17.png

判断后

截屏2020-04-23 下午3.18.25.png

比较T[i]和T[j]，但是i=0,则表示[0,1]这个范围[a]智能从1的位置开始；
j++，i++，所以i=1，j=2
并且更新next[j]=i；则next[2] = 1；

比较T[i]!=T[j]，所以将i的位置回退到a之后，那么i = next[i]=0，

此时，i = 0，i++，j++，next[3] = 1;
比较T[i]==T[j],i++，j++，next[4] = 2;

此时i = 2，j = 4，T[i] = T[j]，i++，j++，next[5] = 3;

此时i = 3, j = 5,T[i] = T[j],i++,j++ ,next[6] = 4;

此时i = 4, j = 6,T[i] != T[j],i = next[4] = 2;

……
以此类推

注意：我们这里找的next数组跟主串没有任何关系，next数组中的值都是在模式串中获取得到的，不要将next与主串进行联系

下面通过代码来写一下如何实现KMP模式串匹配算法

//kmp模式串匹配算法
//1、通过计算返回串T的next数组
//注意T[0]中存储的是字符串的长度，真正的字符内容从T[1]开始;
void get_next(String T,int *next){
    int i,j;
    //i为回退的数组T下标，j为next的下标对应的回退值
    i = 0;
    j = 1;
    //数组第1个值的回退值为0
    next[1] = 0;
    //遍历字符串T
    while (j<T[0]) {
        //计算模式串对应每个字母的回退到那个位置
        if(i == 0 || T[i] == T[j]){
            i++;
            j++;
            next[j] = i;
        }else{
            //如果字符串值不想等，则i值回退；
            i = next[i];
        }
    }
}

通过执行一遍代码，可以更清楚的了解到next数组的实现以及原理，这是一个比较绕的过程。

//KMP匹配算法
//返回子串T在主串S中的第pos个字符后的位置，不存在返回0
int Index_KMP_1(String S,String T,int pos){
    //i是主串当前位置的下标，j是模式串当前位置的下标
    int i = pos;
    int j = 1;
    //定义一个空的next数组，用来存放模式串的每个位置的回退值
    int next[MAXSIZE];
    //对next数组赋值
    get_next(T, next);
    //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
    //若i小于S长度并且j小于T的长度是循环继续;
    while (i<=S[0]&&j<=T[0]) {
        //如果两字母相等，继续
        if(j == 0||S[i] == T[j]){
            i++;
            j++;
        }else{
            //如果不匹配时，j回退到合适的位置，i值不变
            j = next[j];
        }
    }
    //当j大于模式串的长度时，就证明已经找到了匹配的字符串，那么i的值也在与模式串对应的最后一个字母上，因此需要将i减去模式串的长度，来得到开始符合匹配的起始位置
    if(j>T[0]){
        return i-T[0];
    }else{
        return -1;
    }
}

第20行代码就使用到了next数组中的值，当发现不匹配时，模式串会在第next[j]的位置开始与主串中第i个位置进行匹配，从而减少多余的判断，以此来对算法进行优化。

打印结果:

15876275371042.png

KMP模式匹配算法next数组优化

当模式串中有较多相同的子串时，上面的方法还是会进行多次无所谓的比较；
例如：主串:aabaaacd 与模式串aaacd进行匹配，当知道模式串中第三位与主串中第三位不相同，那么模式串会前移一位与主串的第三位相比，但是我们已经知道a和b不想等，没有必要往后前移一位，为什么不直接向前移动三位

因此，在进行i++和j++之后，我们需要对T[i]和T[j]进行比较，比较两个数是否相等，相等时，将next[j] = next[i],不想的时，将next[j] = i

代码：

void get_nextVal(String T,int *nextVal){
    int i,j;
    //i为回退的数组T下标，j为next的下标对应的回退值
    i = 0;
    j = 1;
    //数组第1个值的回退值为0
    nextVal[1] = 0;
    //遍历字符串T
    while (j<T[0]) {
        //计算模式串对应每个字母的回退到那个位置
        if(i == 0 || T[i] == T[j]){
            i++;
            j++;
            //如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
            if(T[i]!=T[j])
                nextVal[j] = i;
            else
                //如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
                nextVal[j] = nextVal[i];
        }else{
            //如果字符串值不想等，则i值回退；
            i = nextVal[i];
        }
    }
}

最后将所有的结果打印：

15876290771362.png

KMP算法比较绕，最好通过手写画图和将代码的过程走几遍，去细细的品。