KMP算法最详细分析！！

示例如下&＃xff1a;

主串&＃xff1a;  a b a b c a b c a c b a b

模式串: a b c a c

匹配过程如下:

第一次匹配&＃xff1a;

这个时候&＃xff0c;如果不用KMP&＃xff0c;而是用BF&＃xff0c;那么我们的做法很明显:

尝试模式串的第一个字符和主串的第二个字符进行匹配。

很明显&＃xff0c;这是多余的&＃xff0c;这是肯定不成立的&＃xff0c;而next数组直接告诉我们&＃xff0c;跳过这一步&＃xff0c;直接如下

这就是next的作用&＃xff0c;如果还不明显&＃xff0c;你再看上图&＃xff0c;模式串的第五位是c和主串相对位置的b不匹配&＃xff0c;那么按照BF算法&＃xff0c;我们需要

再用主串的第四位和模式串的第一位比较&＃xff0c;但是&＃xff0c;很舒服&＃xff0c;next数组告诉我们不用这样&＃xff0c;直接如下

以上就是next的作用&＃xff0c;跳过无用的匹配。

首先&＃xff0c;什么是next数组&＃xff1a;

上述模式串的next数组如下:

a b c a c

0 1 1 1 2

简而言之&＃xff0c;每个字母x对应的next数组值是这样的出来的&＃xff1a;x前的子串和主串的前几个字母相同&＃xff0c;则只需要比较x和主串的第y个元素就好了&＃xff0c;那么这个y就是next[x的索引]的值。

下面引入求next数组的算法:

next存储起始从1开始

void GetNext(string s,int next[])//s是模式串

{

    int i&＃61;1,j&＃61;0;next[1]&＃61;0;

    while(i

        if(j&＃61;&＃61;0||s[i]&＃61;&＃61;s[j]){

            i&＃43;&＃43;;j&＃43;&＃43;;

            next[i]&＃61;j;

        }

        else{

            j&＃61;next[j];//这一步很关键&＃xff0c;他起到的作用就是刚才上面讲到的配对失败之后&＃xff0c;直接跳到指定的位置

        }

    }

}

既然已经得到next数组了&＃xff0c;那么实际操作就很简单了&＃xff0c;附上KMP代码:

int KMP(string s,string t,int pos)//参数分别是主串&＃xff0c;模式串&＃xff0c;求模式串在主串第pos个字符之后的位置

{

    int i&＃61;pos,j&＃61;1;

    while(i

        if(j&＃61;&＃61;0||s.data[i]&＃61;&＃61;t.data[j]){

            i&＃43;&＃43;;j&＃43;&＃43;;//均后移一位

        }

        else j&＃61;next[j];//找到适当的位置

    }

    if(j>t.length())return i-t.length();//匹配成功

    else return -1;

}