kmp算法复杂度o m?希尔排序算法?KMP算法学习总结(3)

换个角度，注意到在每次循环中，无论 if 还是 else 都会修改 j 的值且每次循环仅对 j 进行一次修改，所以在整个while中 j 被修改的次数即为getNext函数的时间复杂度。

每次成功匹配时，++i; ++j; , 由于 ++i 最多执行 m-1 次，故++j也最多执行 m-1 次，即 j 最多增加m-1次；

对应的，只有在 j=next[j]; 处 j 的值一定会变小，由于j 最多增加m-1次，故 j 最多减小m-1次。

综上所述，getNext函数的时间复杂度为O(m)，若带匹配串S的长度为n，则kmp函数的时间负责度为O(m+n)。

7、kmp的应用优势

①快，O(m+n)的线性最坏时间复杂度；

②无需回朔访问待匹配字符串S，所以对处理从外设输入的庞大文件很有效，可以边读入边匹配。

以上就是关于kmp算法的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-8680-3.html