史上最透彻的KMP算法讲解

http://mp.weixin.qq.com/s/XzcAAspIDoQaRlfycsDrRw

1

字符串匹配是经典的KMP算法。下面以字符串"BBC ABCDAB ABCDABCDABDE"为例，查找是否包含串"ABCDABD"？

图一

2

     首先如上图，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜词"ABCDABD"的第一个字符，B与A不相等，所以后移动。

图二

3      上图中，D与空格不相等，但是它有前缀AB与后缀AB相当，KMP的思想就是利用最长的公共前缀与最长公共后缀相等，来加快每次不相等时移动的距离，来提高搜索效率。

4

     要做到这一点，就是要生成一个next匹配数组，next匹配数据来决定匹配的最大长度。如图二。查next数组可知，最后一个匹配字符B对应的"部分匹配值"为2，因此后移动的位数：移动位数 = 已匹配的字符数 - 对应的部分匹配值。因为 6 - 2 等于4，所以将搜索词向后移动4位。

下面是next数组和匹配算法参照代码。

精彩内容

#include <iostream>

#include <cstring>

using namespace std;

const int N = 1000002;

int next[N];

char S[N], T[N];

int slen, tlen;

void getNext()

{

    int j, k;

    j = 0; k = -1; next[0] = -1;

    while(j < tlen)

        if(k == -1 || T[j] == T[k])

            next[++j] = ++k;

        else

            k = next[k];

}

/*

返回模式串T在主串S中首次出现的位置

返回的位置是从0开始的。

*/

int KMP_Index()

{

    int i = 0, j = 0;

    getNext();

    while(i < slen && j < tlen)

    {

        if(j == -1 || S[i] == T[j])

        {

            i++; j++;

        }

        else

            j = next[j];

    }

    if(j == tlen)

        return i - tlen;

    else

        return -1;

}