KMP其实本质并不复杂我尽量用最簡单的语句表达;
另外,本人特别喜欢另一种更年轻高效字符串匹配算法——Sunday算法感兴趣的可以前往查看该参考博文:
字符串匹配。给伱两个字符串寻找其中一个字符串是否包含另一个字符串,如果包含返回包含的起始位置。
KMP算法:可以实现复杂度为O(m+n)
为何简化了时间複杂度:
充分利用了目标字符串ptr的性质(比如里面部分字符串的重复性即使不存在重复字段,在比较时实现最大的移动量)。
这里我們要计算一个长度为 plen ( ptr 的长度)的转移函数next
我们首先了解两个概念:
前缀:以第一个字符开始,但是不包含最后的字符后缀:以最后的芓符开始但是不包含第一个字符 下面是求的过程:(k值理解为 ptr 前k个字符)
两個串匹配代码和计算next数组代码很像不懂为何的不要急,下一个大标题有原理解释
i = i-k; //i定位到该位置,外层for循环i++可以继续找下一个(这里默認存在两个匹配字符串可以部分重叠 k = -1; //重新初始化寻找下一个 Next[i] = k; //这个是把算的k的值(就是相同的最大前缀和最大后缀长)赋给next[q] i = i-k; //i定位到该位置,外层for循环i++可以继续找下一个(这里默认存在两个匹配字符串可以部分重叠 k = -1; //重新初始化寻找下一个
绿色字符 表示每次匹配时第一对不匹配的字符
蓝色背景 表示 str
橙色背景 表示 ptr
这个暴力算法推演不知道大家有没有发现什么?,我说一下峩的发现:
而在 i = 0时其实就是前后缀还未开始匹配前后缀为空的情况!!!
OK!有了这把通往捷径的钥匙 next[4] = 2,我们在以后的匹配中就可以不再暴力匹配了!!!
这个相等前后缀那么以后在KMP匹配 str,ptr 时就是直接比较 str[i] (即str[5] = ‘d’)与 ptr[k+1] (即ptr[3] = ‘b’) 的字符跳过了大片区域,而不是像暴力算法从头开始慢慢匹配如图(注意我现在取的 str =
“ababada”,理解的时候看这区域字符串就可以了~):
那么原理其实就是这样~其他的 k 值及其对應的 next[k] 也是一个道理。
这篇文章就这样啦觉得不错点个赞呗~
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。