Knuth-Morris-Pratt算法（简称KMP），是一种高效的字符串匹配算法

相较于暴力匹配O(mn)的时间复杂度，KMP的算法时间复杂度为O(m+n)，性能上有极大的提升，KMP算法极大的减少了不必要的回溯过程。

假定搜寻的文本串下标索引是i，模式串下标索引是j，KMP算法在匹配过程中，文本串下标i会一直递增，直到结束，不会回退。

一.NEXT数组应用

NEXT数组是KMP算法的核心，它指向当文本与模式串失配时模式串将要回退到的位置。

假定模式字符串为 aabaab，那么这个模式串的NEXT是(暂且不管怎么获得的){-1,0,1,0,1,2}

当模式串在第0位发生失配，文本指针i向后移动一位

当模式串在第1位发生失配，模式串指针回退到第0位

当模式串在第2位发生失配，模式串指针回退到第1位

当模式串在第3位发生失配，模式串指针回退到第0位

当模式串在第4位发生失配，模式串指针回退到第1位

当模式串在第5位发生失配，模式串指针回退到第2位

例：寻找字符串‘aababaabaaba’中’aabaab’首次出现的起始位置，那么匹配过程是这样的：

当模式串在第4位发生失配，模式串指针回退到第1位

当模式串在第1位发生失配，模式串指针回退到第0位

当模式串在第0位发生失配，文本指针i向后移动一位

匹配完成，获取’aabaab’首次出现的起始位置为5

二.制取NEXT数组

重新观察一下模式串’aabaab’的NEXT数组

当j=5的位置发生失配时，next数组指示模式串指针j回退到2位置

观察j=5位置，可以发现

substr[j-1] = substr[next[j-1]] => substr[4] = substr[next[4]] => substr[4] = substr[1]

substr[j-2] = substr[next[j-2]] => substr[3] = substr[next[3]] => substr[3] = substr[0]

也就是说 j = 5的前两个元素与next[5]所指向的2的前两个元素相等

正因为这样，在j=5位置发生失配时，j指针才能直接回退到2

例如用这个模式串去搜索aabaacaabaab

在j=5的位置发生失配，j指针回退到2

回退后我们可以保证模式串j=0,j=1位置的字符必定与文本i=3,i=4位置的字符相等，所以只需判断移动后模式串j位置的字符与文本i位置的字符是否相等即可

我们取得‘aabaab’的所有前缀，无视每个前缀的最后一个元素，每个前缀除去最后一个元素，后缀与前缀的重叠次数就是next的值，第一个next值固定为-1，第二个next值固定为0

S NEXT

a -1（固定）

aa 0（固定）

aab 1（aa的前后缀有 a、a）（相同的有一个）

aaba 0（aab的前后缀有a、aa、b、ab）（没有相同的）

aabaa 1（aaba的前后缀有a、aa、aab、a、ba、aba）（相同的有一个）

aabaab 2（aabaa的前后缀有a、aa、aab、aaba、a、aa、baa、abaa）（相同的有两个）

这样，我们就求得了NEXT数组={-1, 0, 1, 0, 1, 2}

再次观察

可知，如果我们想知道next[j+1]的值，只需判断T[j]是否等于T[ next[j] ]

1.我们可以定义一个临时变量：k = next[j]

2.如果k = -1，那么next[j + 1] = 0，否则继续步骤3

3.如果T[j] == T[k]，那么next[j+1] = k + 1，否则继续步骤4

4.如果T[j] != T[k]，那么k=next[k]，重复判断步骤2

例：J表示模式串索引，T表示模式串数组，N表示模式串NEXT数组

一、j = 2, N[j]=？

假定 k = N[j – 1] = N[1] = 0

判断 T[j – 1] 是否等于 T[k]：T[j-1] = T[1] 是否等于 T[k] = T[0]

T[1] = T[0] => ‘a’ 等于 ‘a’

因为T[1] = T[0]，所以N[j] = k + 1 => N[2] = 1

二、j = 3, N[j]=？

假定 k = N[j – 1] = N[2] = 1

判断 T[j – 1] 是否等于 T[k]：T[j-1] = T[2] 是否等于 T[k] = T[1]

T[2] = T[1] => ‘b’ 不等于 ‘a’

所以k = N[k] = N[1] = 0

再次判断 T[j – 1] 是否等于 T[k]，T[2] = T[0] => ‘b’ 不等于 ‘a’

所以k = N[k] = N[0] = -1

因为k = -1，所以N[3] = 0

制取Next数组代码：

size_t npos = static_cast<size_t>(-1);

sizr_t* KMP_MakeNext(const char* substr, size_t len)
{
    size_t* next = new size_t[len];//next数组是new的，没使用智能指针，所以用完注意释放
    next[0] = npos;

    int j = 0;
    int k = npos;

    while(j < len - 1)
    {

        if(k == npos || substr[j] == substr[k])
        {
            ++j;

            if(k == npos) k = 0;
            else ++k;

            next[j] = k;

        }
        else
        {
            k = next[k];
        }

    }

    return next;
}

四.字符串匹配

既然已经获得了Next数组，那么字符串匹配就是一件小事了。

以下便是使用NEXT进行字符串匹配的代码

size_t KMP_Find_Count(const char* findstr, const char* substr)
{
    size_t find_len = strlen(findstr), subs_len = strlen(substr);

    if(subs_len == 0 || find_len < subs_len) return 0;

    size_t* next = KMP_MakeNext(substr, subs_len, false);

    size_t count = 0;

    size_t j = 0, k = 0;
    while( j < find_len )
    {
        if(k == npos || findstr[j] == substr[k])
        {
            //指示后移，或匹配成功
            ++j;
            if(k == npos)
            {
                k = 0;
            }
                else
            {
                ++k;
            }

            if(k == subs_len)
            {
                //子串匹配成功，计数+1，并回溯到匹配成功的位置，继续匹配
                ++count;
                k = next[k - 1];
                --j;
            }
        }
        else
        {
            k = next[k];
        }
    }
    delete[] next;
    return count;
}