简单易懂的KMP算法理解

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了简单易懂的KMP算法理解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3557字，纯文字阅读大概需要6分钟。

内容图文

KMP算法是由三大佬研发出来的用于匹配字符串的算法。

解决在一个大串中找与模板串相同的子串。

解决上诉问题，有一个简单且好理解的方式：

将大串前(M-N+1)个字符(M代表大串长度，N代表模板串的长度)依次与模板串的第一个字符比较，不匹配则大串当前比较的字符不是模板串的第一个字符则需要匹配下一个大串字符，若匹配，则大串当前比较的字符是模板串的第一个字符则需要将大串当前字符的下一个字符和模板串的下一个字符进行比较，依次类推，直到匹配全找到子串或者找不到。

这样的方法优点是简单好实现，但是显然会花费许多时间，举一个最坏情况下的例子:

大串:aaaaaaaaaaaaaaaaaaaab

模板串:aaaaab;

这个例子在最后一次匹配才成功找到，而前面的每次匹配都将模板串的每个字符都遍历了一次，如果大串长度M，模板串长度N，那么花费的时间共为O((M-N+1)*N);数量级可看成为二次方级的。在数据量稍微大些的情况下会很慢。

 

 

KMP算法便是用来解决这种缺点的。

KMP算法关键之处其实就是记录模板串中的前缀子串中的相同的最长前、后缀的长度。这样如果模板串中途匹配失败后，模板串匹配大串后移将不只是一位。而是移动直至匹配失败前的前缀子串(这里用x代替)中的前缀和其(x)后缀重叠，这样移动的位数为两相同的前后缀位置差。如果这样做是正确的，不就是节省了一些时间吗？那么接下来就解释下为什么这样做是正确的：

如果一个长度为N模板串配成功后，向后移动n位前N-n位依然能匹配对，那么会有什么性质？从第一次匹配最后一个字符往前算起长度N-n的子串是什么？其实就是模板长度为N-n的前后缀(因为两次都与大串匹配对了，这两个前后缀显然是相等的)。反过来说，若是一个模板串有多组相等的前后缀，如有三组长度分别为N-n1,N-n2,N-n3，那么模板串匹配成功后向后分别移n1,n2,n3个位置后依然有N-n1,N-n2,N-n3位能全匹配。

把这个应用到模板串匹配失败时候的处理：将匹配失败前的前缀子串(x)看成上述讲的成功匹配的小模板串,这个模板串可以根据已有的（如果有)相同前后缀的长度移动，为保证不漏匹配，只需要取最长前后缀(这样可以使得移动最小)的长度决定移动位数，即可保证这种匹配方法的正确性。

上述便是KMP的一个重点所在。

 

 

还有一个重点便是如何比较快的找到模板串前缀子串中的相同最大前后缀。这个也是KMP的难点：

事实上，如果模板串很长的话，要找到它的最长相同前后缀其实也不省事。若模板串短显然就容易了，那么不妨找个几个例子看看短模板串前后缀：

abca

显然最长前后缀为a

abcab

最长前后缀为ab

abcabc

最长前后缀为abc

上面三个例子中的下两个是由第一个例子增加一个字符扩展而成的，这样做的目的是展示一种情况：如果一个字符串最长相同前后缀(这里用cnext[n-1],n-1代表前缀最后一个字符的数组下标)长度为n，那么该字符串增加一个字符后最大前后缀最长上限是n+1。而达到这个上限的条件是增加的字符和原字符串的cnext[n-1]的下一个字符相同，这种匹配成功的情况下便是只匹配一次字符就可以得出最大前后缀的长度。但事实上更多情况是匹配失败，如果匹配失败该怎么做？举一个例子：

abacabab

abacaba这个最长相同前后缀为aba

之后加了一个b之后我们会匹配aba后面的c是否与b匹配，这个时候不匹配，显然最长相同前后缀已经不可能有比aba长了，既然如此，我们是否可以把abacabab看成abab呢？答案是可以的，为什么呢，因为现在最长相同前后缀只能在abacabab中的小于等于3长度的(aba的长度)后缀(bab)中找最大后缀（这里用cnext[7]代替），而abab后缀集合一定包含cnext[7];那么我们在新增字符不匹配的情况下就可以将abacabab看成abab去找其最长相同前后缀，以此类推直到找到最长相同前后缀或者找不到为止。

模拟下剩下的步骤：这个时候abab中的aba最长相同前后缀为a，将b与前缀a后面的b比较，相同，则abab最长相同前后缀为ab。

KMP算法是用一个和模板串相同长度的数组next[]保存每个模板串前缀中的最长相同前后缀的长度（next[n-1]的值是长度为n的前缀子串对应的最长相同前后缀的长度)，下面给出求next[]的代码：

 

void makeNext(const char P[],int next[])

{

    int len= strlen(P);

    next[0] = 0;

    for (int q = 1,k = 0; q < len; ++q)

    {

        while(k > 0 && P[q] != P[k])

            k = next[k-1];

        if (P[q] == P[k])

        {

            k++;

        }

        next[q] = k;

    }

}

 

内容总结

以上是互联网集市为您收集整理的简单易懂的KMP算法理解全部内容，希望文章能够帮你解决简单易懂的KMP算法理解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---