大学数据结构课件10.kmp.ppt

文档介绍：kmp算法
kmp算法是一种改进的字符串匹配算法, ,因此人们称它为克努斯——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串p(pattern),定义一个next函数。next函数包含了模式串本身局部匹配的信息。
KMP算法的基本思想
假设在模式匹配的进程中,执行S[i]和P[j]的匹配检查。若S[i]=P[j],则继续检查S[i+1]和P[j+1]是否匹配。若S[i]<>P[j],则分成两种情况:
若j=1,则模式串右移一位,检查S[i+1]和P[1]是否匹配;
若1<j<=m,则模式串右移j-next(j)位,检查S[i]和P[next(j)]是否匹配。
重复此过程直到 j=m 或 i=n 结束。
一般的KMP算法
假设
主串: s: ‘s(1) s(2) s(3) ……s(n)’
模式串:p: ‘p(1) p(2) p(3)…... p(m)’
现在我们假设主串第i个字符与模式串的第j(j<=m)个字符‘失配’(不同)后,主串第i个字符与模式串的第k(k<j)个字符继续比较(为什么?)
此时,s(i)≠p(j), 有
主串:s(1) … s(i-j+1) s(i-j+2) … s(i-1) s(i) ……
|| (相配) || ... || ≠(失配) (1)
匹配串: p(1) p(2) ... p(j-1) p(j) …
由此,我们得到关系式:
‘p(1) p(2) … p(j-1)’= ’ s(i-j+1) s(i-j+2) … s(i-1)’(2)
一般的KMP算法
由于s(i)≠p(j),接下来如果将s(i) 与p(k) (k<j)继续比较,则模式串中的前(k-1)个字符子串必须等于主串第i个字符前的(k-1)个字符子串,并且不可能存在 k'>k (k<j)也满足上述关系。即:
‘p(1) p(2) p(3)…p(k-1)’= ’s(i-k+1)s(i-k+2)…s(i-1)’(3)
即:
主串: s(1)…s(i-k+1) s(i-k +2) … s(i-1) s(i) …
|| (相配) || …|| ? (有待比较)
匹配串: p(1) p(2) … p(k-1) p(k)
由(1)、(2)式可知,若
‘p(1) p(2) … p(k-1)’= ’p(j-k+1)p(j-k+2) … p(j-1)’(4)
则(3)式一定成立。(为什么?)
一般的KMP算法
因为: s(i)≠p(j)
主串:s(1) … s(i-j+1) s(i-j+2) … s(i-1) s(i) ……
|| (相配) || ... || ≠(失配) (1)
匹配串: p(1) p(2) ... p(j-1) p(j) …
‘p(1) p(2) … p(j-1)’= ’ s(i-j+1) s(i-j+2) … s(i-1)’(2)
(2)式说明:主串中第i个字符前的j-1个字符子串等于匹配串中第j个字符前的j-1个字符子串。因为 k < j , 所以主串中第i个字符前的k-1个字符子串必然等于匹配串中第j个字符前