C语言kmp算法简单示例和实现原理探究(2)
复制代码 代码如下: kmp-matcher(T, P) n-length[T] m-length[P] pi-compiter-prefix-function(P) q-0 for i-1 to n do while q0 and P[q+1]!=T[i] do q-pi[q] //前缀的前缀... if P[q+1]==T[i] then q
复制代码 代码如下:
kmp-matcher(T, P)
n<-length[T]
m<-length[P]
pi<-compiter-prefix-function(P)
q<-0
for i<-1 to n
do while q>0 and P[q+1]!=T[i]
do q<-pi[q] //前缀的前缀...
if P[q+1]==T[i]
then q<-q+1
if q==m
then print “Pattern occurs with shift”i-m
q<-pi[q]
这两段代码思想完全相同,如果和前缀不同就比较前缀的前缀…，比较巧妙。如果kmp有难理解的地方，估计就是这段伪码的了。
KMP算法的时间复杂度为O(n+m)。
这里需要强调一下，KMP算法的仅当模式与主串之间存在很多部分匹配情况下才能体现它的优势，部分匹配时KMP的i不需要回溯，否则和朴素模式匹配没有什么差别。
- 上一篇：汇编语言常见错误信息中文注解
- 下一篇：c++ *运算符重载
精彩图集
精彩文章