Flash and 网络工程师

如果你确实只是想完成练习题  那看看这个解答吧 反正我算是看明白了

当用KMP算法时,进行查找时扫描指针的动作就只依赖于模式,而与目标无关.

所以解此类题时,只将焦点集中于模式串并根据失效函数定义公式计算即可.

公式如下: f(j)=K 或-1.

取Ｋ时，满足的条件为：０＜＝Ｋ＜Ｊ，且使得Ｐ０．．ＰＫ＝Ｐ（Ｊ－Ｋ）．．Ｐ（Ｊ）．　

（Ｊ依次从０到Ｎ－１进行计算．）

对于第一串：　aabbaaccaabb

　　　分别编号：０　１　２　３　４　５　６　７　８　９　１０　１１

J=0:K无值,f(0)= -1

J=1:K=0, p0=p1, f(1)=0

J=2:K=0,1,p0<>p2,p0p1<>p1p2,f(2)= -1

J=3:K=0,1,2,p0<>p3,p0p1<>p2p3,p0p1p2<>p1p2p3, f(3)=-1

J=4:K=0,1,2,3, p0=p4,p0p1<>p3p4,p0p1p2<>p2p3p4;p0p1p2p3<>p1p2p3p4, f(4)=0

J=5,K=0,1,2,3,4:p0=p5,p0p1=p4p5;p0p1p2<>p3p4p5,p0p1p2p3<>p2p3p4p5,

p0p1p2p3p4<>p1p2p3p4p5 , f(5)=1

J=6,K=0,1,2,3,4,5: p0<>p6,p0p1<>p5p6;p0p1p2<>p4p5p6,p0p1p2p3<>p3p4p5p6

aabba<>bbaac, aabbaa<>abbaac f(6)= -1

J=7,K=0,1,2,3,4,5,6, a<>c, aa<>cc,aab<>acc.aabb<>aacc,aabba<>baacc,aabbaa<>bbaacc

aabbaac<>abbaacc f(7)= -1

J=8,K=0,1,2,3,4,5,6,7, a=a, aa<>ca,aab<>cca,aabb<>acca,aabba<>aacca,aabbaa<>baacca,

aabbaac<>bbaacca, aabbaacc<>abbaacca f(8)=0

J=9,K=0,1,2,3,4,5,6,7,8. a=a,aa=aa,aab<>caa, aabb<>ccaa,aabba<>accaa

aabbaa<>aaccaa,aabbaac<>baaccaa,aabbaacc<>bbaaccaa,aabbaacca<>abbaaccaa

f(9)=1

J=10,K=0~9,a<>b,aa<>ab,aab=aab,aabb<>caab,aabba<>ccaab,aabbaa<>accaab

aabbaac<>aaccaab, aabbaacc<>baaccaab,aabbaacca<>bbaaccaab,

aabbaaccaa<>abbaaccaab. f(10)=2

J=11,K=0~10, a<.b,aa<>bb,aab<>aabb,aabb=aabb,aabba<>caabb,aabbaa<>ccaabb

aabbaac<>accaabb,aabbaacc<>aaccaabb,aabbaacca<>baaccaabb

aabbaaccaa<>bbaaccaabb, aabbaaccaab<>abbaaccaabb

f(11)= 3

综上所述,所求失效函数的值为 (-1,0,-1,-1,0,1,-1,-1,0,1,2,3)