以下是引用恒翔在2004-10-8 15:13:45的发言：
请根据改进KMP算法计算以下三个模式串的对应的Next值？
aabbaaccaabb
abcdcbabcdcba
abacadacaba
最好能够根据该题进行详细的说明？不胜感激
对于第一串： 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)
晕,计算太麻烦,不知道有没有粗心的地方,请楼上自己再算一下.
[em06][em06][em06]
[此贴子已经被作者于2004-10-8 17:31:29编辑过]
