kmp 算法

KMP是一种字符串匹配优化的算法,假设要查找的字符串长度假设长度是M, 被查找的字符串假设长度是N。那么普通的算法的平均效率即是O(M*N), 而kmp算法的平均效率是O(N)。

kmp之所以能做到O(N), 就是说它能记录已经匹配过的字符串,无需重头开始进行比较,也就是没有回朔。网上很多关于kmp算法有不少文章,但是大多都是讲得一知半解。这里推荐一篇讲解kmp略屌的博客, 看完这篇就不用看其它的博客。

Knuth-Morris-Pratt algorithm

文章主要说明的核心思想

1) 如何构建查找表

2) 证明构建查找表的正确性

下面是我参照这篇文章的实现代码:

kmp c code