KMP算法的理解，伪代码，c代码实现_kmp算法实现的框架,可以用伪代码、流程图形式给出

作者：爱喝兽奶帝天荒 | 2024-07-29 22:40:35

踩

kmp算法实现的框架,可以用伪代码、流程图形式给出

1、字符串问题形式化定义：假设文本是一个长度为n的T[1..n]，而模式是一个长度为m的数组P[1..m]，其中m<=n，如果有T[s+1..s+m]==P[1..m]，那么就称模式P在T中出现。s为有效偏移，否则称为无效偏移。

2、方法：首先基于模式进行预处理，然后找到所有有效偏移（匹配）。

几种方法的预处理时间和匹配时间

朴素算法 0 O((n-m+1)*m)

Rabin-Karp O(m) O((n-m+1)*m)

有限自动机算法 O(m|所有有限长度字符串的集合|) O(n)

KMP O(m) O(n)

3、朴素字符串匹配算法：通过循环的方式找到所有有效偏移s。有效偏移s的可能有n-m+1个，每次匹配需要m次，因此共需匹配（n-m+1)*m次。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/900916