算法笔记------KMP算法

本文主要是介绍算法笔记------KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

时隔俩个月，之前学的时候觉得贼他妈难的KMP算法终于看懂了，废话不多说，马上动手，马上动手。

先说前提条件，如果给我们俩个字符串P：

ab和另一个更短的字符串S：ababf，让我们证明字符串S是否在P中出现过，如果出现过让我们输出其初始位置的下标

这种情况我们可能第一时间想到的是暴力做法

for(int i = 1; i <= n; i++) {
    bool falg = true;
    for(int j = 1; j <= m；j++) {
        if(s[i] != p[j]) {
            flag = false;
            break;
        }        
    }
}

但是这种暴力写法的时间复杂度为O(n*m)数据量稍微大一点就非常容易超时，故我们需要使用KMP来优化它，KMP算法的时间复杂度为O(n + m)比暴力解法低了一个数量级

接下来我先发出一张图片介绍下KMP算法中最最最核心的部分

在这里我们可以惊奇的发现红色边框和黄色边框里的字符串是相同的，在这里我们叫红色边框为公共前缀，而黄色边框为公共后缀，KMP算法中我们就是不断的移动公共前后缀

最后在实现字符串的匹配的，这也是为什么KMP中要有next数组的存在。

我们先来解释一下KMP中用到的next数组的意义吧，例如next[ i ]的意义是字符串P前i个字符串中的最长公共前后缀的长度，例如我们上面图片的最长公共前后缀的长度就是2，

因此我们next数组中存储的是长度，而不是下标哦。

这边我先放出KMP中匹配的代码

for(int i = 1, j = 0; i <= m; i ++)
{
    while(j && p[j+1] != s[i]) j = ne[j];//该操作就是上图中的匹配操作
    if(p[i+1] == s[j]) j ++;
    if(j == Plen)
        cout << i - Plen;//这一步很好看懂，字符串S的指针i减去一个P的长度就是初始下标
        //因为已经匹配完成所以i指的是字符串s中的字符串p的下标的下一位
}

而我们在上面的代码中用的是ne而不是next数组，是因为c++的一些库中已经有了next这个名字，为了以防万一我们可以改变数组名为ne，上面匹配操作相对next数组来说没有那么的难，接下来给出求next数组的代码，总体来说和匹配的代码是十分的相似的，但是如果自己有条件的话还是在画图或者草稿纸上模拟一下

for(int i = 2, j = 0; i <= Plen; i ++)
{
    while(j && p[i] != p[j+1]) j = ne[j];
    if(p[i] == p[j+1]) j ++;
    ne[i] = j;
}

从上图我们知道，求next数组的过程中我们是把字符串p与他自己进行比较的一个过程，从前往后逐步的求出了每一个下标的next数值，到此我们已经把kmp的所有过程讲完了。

这篇关于算法笔记------KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！