KMP算法的主要功能

解决在字符串中的模式定位问题，就是在主串S中寻找模式串T，如果找到返回T在S中的具体位置，否则返回默认值-1。

朴素算法与KMP算法的本质区别

现在给定一个场景（能体现KMP算法的优越性的），如下图所示

当遇到此类情况时，两种算法的所作所为，如下

1.朴素算法：将主串s回溯到字符B所在位置，将模式串T整体向后移动一位，然后进行下一次匹配。

2.KMP算法：保持主串s的位置不变，将模式串T整体向后移动三位，然后进行下一次匹配。

总结：我们可以很明显的发现，朴素算法比较“笨”，对于模式串T来说，“ABCE”的首字母“A”与后面的串“BCE”中任意一个字符都不相等，根据第一次匹配得知“BC”与主串中的第二三位相匹配，也就是说“A”不可能与主串的第二三位相匹配。

那么朴素算法相对于KMP算法来说，将会进行两次无意义的匹配，增加算法的时间复杂度。而KMP算法能够做到避免无意义的匹配，显然是通过某种手段保存了第一次匹配的相关信息，这是我们接下来要探索的东西！

NEXT[]——前奏

相信大家在上述的几张图片中已然能看出KMP算法的核心思想“通过已经匹配的有效信息，保持指针s不回溯，通过修改指针t ,让模式串尽可能移动到有效位置。”

那么我们要保存什么样的有效信息呢？我带大家来探索一下！

第一种情况

（数字为坐标）如图，C和D不匹配了，我们要把t移动到哪里？

请大家忽略上述移动后仍旧不匹配的情况，这是有意为之，想告诉大家KMP不是一次就能匹配成功的算法。

显然我们能够发现要把t移动到位置1处，这是因为模式串中T[2] == S[2], T[0] == T[2]能得出
T[0] == S[2],既然T[0]与S[2]已经匹配了，我们当然不需要从模式串的位置0处开始比较。

这个留给大家自己思考，如下

第二种情况

（数字为坐标）如图，D和B不匹配了，我们要把t移动到哪里？

显然我们能够发现要把t移动到位置2处，具体原因同上。

留给大家的思考，如下

第三种情况，是我们的老朋友了（很抱歉用的没有坐标的旧图，嘿嘿！）

（数字为坐标）如图，D和E不匹配了，我们要把t移动到哪里？

显然我们要把t移动到位置0处，具体原因已经解释过了（文章开头），这次就不留思考了。

总结，我们不难发现要保存的信息是当t匹配失败时，t要移动到的下一个位置，我们称这个位置为k 。
即我们要保存的信息存放在一个关于t的数组中 ，我们称之为next[] ，每个t有且仅有一个k值与其对应，表示为next[t] = k 。

next[]——正文

通过上面的例子，我们大概可以看出一些规律，t要移动的下一个位置k ，最前面的 k 个字符和 t 之前的最后 k 个字符是一样的！

前面第一个例子，

前面第二个例子，

前面第三个例子，

看到这里我相信大家都会手动求 k 值了，总结得到下图，***为省略意思

都铺垫到这里了，我就可以大胆的把公式给大家列出来了（图片是在别人博客找的，望周知）

上图的 j 和本文的 t 含义相同。现正式引入字符串前后缀概念，前缀指字符串不包含最后一个字符；后缀指字符串不包含第一个字符，我给大家举一个简单的例子，就会明白的很通透！

在这之前我们只知道 k 是匹配失败后，下一步移动到的位置。现在我们给出 k 的完整定义：当 t = 0时，k = -1(稍后解释）;当 t != 0时，k 的值为位置t 之前字符串的最长相等前后缀的长度。（大家可以回看上面的例子验证一下）

到这里大家距离攻克KMP算法就只剩下最后一步了，next[]数组的具体实现，先给大家展示出代码。

void get_next(String T, int* next)
{
    int t = 0;
    int k = -1;
    next[0] = -1;
    while( t < tlen - 1)
    {
        if( k == -1 || T[t] == T[k] )
        {
            next[++t] = ++k;
        }
        else
        {
            k = next[k];
        }
    }
}

通过观察代码，我们发现当T[t] == T[k]时，有next[t+1] = next[t]+1;(别问我为什么和上面的代码不一样）（还有就是别忘了next[t]就是k）我用图片帮助大家理解，如下

当T[t] != T[k]时，k又会如何变化呢？这是KMP算法的重点，请大家集中注意力了！
我们可以先不关心 k = next[k] 这个操作本身，我们想一下这个操作的目的是什么？请大家回看上面的next代码，不就是改变 k 的位置使得下一次的T[t] == T[k]，这难道不像主串与模式串的匹配过程吗？

现在我将上面的图片拆解成主串与模式串的匹配情形

这样看着是不是就觉得很熟悉了，前面我们遇到了那么多的例子，现在是不是闭着眼睛都能熟练的写出 k = next[k] , 然后来进行下一次匹配。

当然这是个一次就成功的例子，但实际操作起来往往遇到的都不是这种一次性成功的，会反反复复的进行 k = next[k] 操作，这里就不给大家举例子了。最重要的是常常使用一次性成功的例子来举例，会让人误以为这本就应该是一次性成功的操作，如果一次过后没成功，可能大家就会怀疑自己是不是理解错了。（至少我个人常常受此困扰）

next[]——改进

如果大家在看文章的基础上，自己理解并进行了一定程度的思考，那么一定会发现一个小问题。（注意了我们现在要回到主串与模式串的匹配上）

注意了 T[t] == T[next[t]] ，T[t] != S[s] ，得T[next[t]] != S[s] 。这代表下一次的匹配是毫无意义的。

这就相当于什么呢？相当于自己买东西要通过一个和自己长得一毛一样的中间商，心里憋屈不说，还费时又费力。解决办法是什么?当然是把他手里的购买渠道抢过来啊，不对文化人怎么能叫抢呢，这叫借！用代码表示出来就是next[t] = next[k]（我猜又有人忘了next[t]就是k 了），当然我们还要在这之前进行一个判断，看他是不是和我长的一毛一样（要不然底气不够），用代码表示出来就是if( T[t] == T[k] )。下面是完整代码展示

void get_nextval(String T, int* nextval)
{
    int t = 0;
    int k = -1;
    nextval[0] = -1;
    while( t < tlen - 1)
    {
        if( k == -1 || T[t] == T[k] )
        {
            t++;
            k++;
            if( T[t] == T[k] )
            {
                nextval[t] = nextval[k];
            }
            else
            {
                nextval[t] = k;
            }
        }
        else
        {
            k = nextval[k];
        }
    }
}

到这里就基本结束了，给大家附上完整的KMP代码

int KMP(String S , String T)
{
    int s = 0;
    int t = 0;
    int nextval[tlen];//tlen是T的长度
    get_nextval(T , nextval);
    while( s < slen && t < tlen)
    {
        if( t == -1 || T[t] == S[s])
        {
            t++;
            s++;
        }
        else
        {
            t = nextval[t];
        }
    }
    if( t == tlen )
    {
        return s-t;
    }
    else
    {
        return -1;
    }
}

最后一个遗留问题：next[0] = -1;是为了当 t 回溯到0的时候，下一次自增从0开始。

大家的评论就是对我最大的支持，以上内容肯定存在大大小小的错误，请大家多多指教，我会虚心接受每一位未来大佬的建议，期待下次相遇。