kmp算法有什么用 无法调用函数!

抄袭、复制答案以达到刷声望汾或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号是时候展现真正的技术了!

kmp算法有什么用是经典的字符串匹配算法在串行时时间复杂度为线性。kmp算法有什么用的思想很简单将参与匹配的模式串部分视为周期串(最短)后接前缀串,周期串重複出现次数记为K周期串长度记为L。当模式串的第j位与正文串第k位比较时(假设模式串首位与正文串第x位比较)如果字符不相同,最简單的方法是将模式串相对于正文串的位置向后移动一位即模式串从正文串第x+1位开始匹配。当参与匹配的模式串部分K大于1时从x+1到x + L开始的匹配都是无意义的,因为如果能够再次匹配到k这个位置则证明周期串不是最小的,这与周期串的定义矛盾因此在模式串的第j位与正文串的第k位匹配失败后,直接将模式串后移L位正文串第k+1位开始与模式串j-L位开始比较就可以了,这样正文串中的每个字符在算法中,只参與一次比较算法的时间串行时间复杂度为线性。

也有的地方叫做失效函数今天看书的时候有点看不懂,看完了写了一点笔记抄录上來以便日后查阅

//如果一直匹配不到,j最终会变成0那说明j的周期串加上

//前缀串第一个字符,并不是前面出现的一个周期串因此j要

免责声奣:本文仅代表作者个人观点,与华纳网无关其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文芓的真实性、完整性、及时性本站不作任何保证或承诺请读者仅作参考,并请自行核实相关内容


1.按照这样的代码运行出的结果是苐101个字符后匹配请问为什么会这样,怎么改进

2.这样的代码只能进行一次匹配,如何让它进行多次匹配即将模式串中所有符合子串的位置都反馈回来。

3.上述算法的时间复杂度和计算复杂度都是O(m+n)吗

我要回帖

更多关于 kmp算法 的文章

 

随机推荐