深入浅出KMP算法

KMP是一种高效的字符串匹配算法，可以在O(n)的时间复杂度内完成子串对主串的匹配，包括寻找子串主串中的出现位置和子串在主串中的出现次数等等
1.KMP算法的工作机制
2.KMP算法证明
3.KMP算法实现
4,KMP算法优化
4.KMP算法练习题

1，KMP算法工作机制

从原始抵消的暴力匹配（BF算法）开始想，我们是怎么进行字符串匹配的：
暴力BF算法就是：从第一位开始从前往后枚举，逐位匹配，复杂度为O(N^2)
举个例子就是下面这样：

但是这显然不是我们想要的，如果凭借人眼来判断我们一定不会这么比较
因为我们至少知道：
子串的开头是1好歹找个是1的位置开始比较吧！
于是实际上，我们更期望省略掉那些明显的冗杂项
但是我们同时知道，我们运用的匹配算法都是逐位匹配的
什么是逐位匹配呢，就是说：
当我们匹配到子串的第i位时，子串的前i-1位已经完全匹配完成
这是很多讲KMP算法的人没讲到的，那就是，前i-1为已经完全匹配
那么如果第i位刚好不匹配，我们还会选择从开头位一位一位往后匹配吗？
很显然，不需要，因为这i-1位都来自于子串自己
很容易想到，如果数据相当大：
那么这些来源于子串自己的前i-1位已经匹配好的位建辉重复匹配多次
比方说：

我们会在第3个时匹配失败，但是我们前面已经有两位匹配成功了
我们不必一位一位枚举，因为我们将会重复用1来匹配本来已经匹配好的2
重点是，我们已经匹配好的位，既然已经匹配好了，再重新匹配，岂不是很亏
所以！！！
我们只要自己匹配一下自己，我们就知道，那些位我们根本不需要再去匹配了！
注意，我们只要自己匹配一下自己，就可以很清楚的去重！
怎么匹配呢，我们要找的是那些我们根本不需要去再次匹配的位！
举个很简单的例子：

1，如果第一位匹配失败，那没办法，下一位还是要从1开始匹配，因为没有已经匹配好的位

2，如果第二位匹配失败，那么我们知道已经匹配好了第一位，但是由于第一位是起始位，而且到第二位就匹配失败，所以我们没办法下一次还是从1开始

3，如果到了第三位，我们匹配失败了，那么我们知道前两位已经匹配成功，所以在母串中必然有一段：…………12…………，此时我们起始位是1，按照BF，我们下一位会比较1和2，但是我们在自我匹配的时候认识了自己，我们知道这一位不等于起始位，必然失败，所以我们跳过，在2后面那一位开始匹配

4，如果我们到了第四位，我们匹配失败了，那么前面必然有：……123，所以我们现在记住！直接跳过23，匹配接下来一位

于是，我们找到了可以不匹配的位，只要我们自我匹配一遍！
除了上面的情况，还有一种情况非常常见：
我们等效的跳过一些位，但是我们需要考虑从子串的哪里开始匹配才不会漏掉情况
就比如：

我们按照上题的思路来：
1，省略
2，省略
3，得前两位：……12，还是选择跳过2

4，重头戏！匹配到了第四位然后匹配失败了，也就是已得前三位：……121，此时我们不应该跳过后面那个一到下一位（反例：3211212132），但是我们也不需要重新匹配，因为可以在自我匹配的时候发现，我们在匹配到第4位失败的时候，正好有s[1]=s3，我们记下来~，直接拿……121后面的位和2(s[2])开始比（已经有一位匹配好了，在自我匹配的时候）

5，接下来，如果到了第5位的时候匹配失败，那么我们知道，前面已经匹配好了：……1212，和上面一样，我们的s[1]=s[3],且s[2]=s[4]，这个时候，我们记下来~，在……1212的下一位用1（s[3]）来匹配，因为前面我们己经记下了第一位和第二位必然完成匹配

我们只要自己把自己给看清楚，当自己在适应环境的时候就知道从哪里开始了

和他人比较前，先看清楚自己

所以，经过我们的处理我们可以节约大量的自我重新匹配的时间！非常NICE

以上就是工作机制，具体如何通过代码实现看第三部分

2，KMP算法证明（觉得前面够清楚了请跳过）

设主串s1[n],子串s2[i],备忘k[i]
1，备忘的正确性：
备忘记为 if(s2[1..a]==s2[b..c]) k[c+1]=a;
求证：s2[c-k[c+1]..c] == s2[a..k[c+1]]
由定义式可以直接得到 >__>
2，不会漏下结果
因为省略的枚举首位都无法与s2[1]匹配
而如果要和s2匹配就必须先和s2[1]匹配
那么省略的必然无法匹配
所以没有漏结果

3，KMP算法实现

终于到了最激动人心的时候了！
根据上面的思路，我们需要先自我扫描一遍存备忘，然后再和主串匹配
我们一般把备忘用next数组表示
next[i]表示当匹配到第i位失败的时候（对于主串，我们保持，不需要回头逐位枚举），对于子串，我们可以自我匹配（首对尾）到多少位（为了不漏下）；
然后，看模板吧> ~ <(模板来自：yxc闫总 )
求nxet数组模板

for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && s[i] != s[j + 1]) j = next[j];    
    //回溯到能匹配上的位置或开头
    if (s[i] == s[j + 1]) j ++ ;
    //匹配上了，指针后移，继续匹配
    next[i] = j;
    //对于整串，记录可以匹配到的位置（记得初始化next[0]=0,next[1]=1）
}

匹配模板

for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s1[i] != s2[j + 1]) j = next[j];
    if (s1[i] == s2[j + 1]) j ++ ;
    if (j == m)
    {
        j = next[j];
        // 匹配成功后的逻辑
    }
}
//是不是和上面特别像！因为他们本质是一样的！

实现起来并不麻烦，重点在于理解KMP算法和里面的DP和回溯思想

4，KMP算法优化

看起来，KMP算法已经是一个O(n)的高效线性算法了，但是，对于有些情况，我们还可以再剪枝！
比如：

对于这种情况，我们如果按照前面的说法，我们就会再拿s[3]的1再比一次，但是我们明明知道1是会匹配失败的！
我们在自我扫描的时候就可以考虑这一点，那就是，在s[1]=s[3],s[2]=s[4]时候，保证s[2+1]!=s[4+1]
只要稍微改一下上面的代码，又可以剪枝不少！

for (int i = 2, j = 0; i <= m; i ++ )
{                                 //  这里↓
    while (j && s[i] != s[j + 1] && s[i+1] != s[j+2]) j = next[j];    
    //回溯到能匹配上的位置或开头
    if (s[i] == s[j + 1]) j ++ ;
    //匹配上了，指针后移，继续匹配
    next[i] = j;
    //对于整串，记录可以匹配到的位置（记得初始化next[0]=0,next[1]=1）
}

5，KMP练习题

明天起来再更，先收藏啦！

码字不易，如有问题，欢迎讨论