字符串匹配过程图示
2016-04-26 08:49:45 7 举报
为你推荐
查看更多
这是为了写一篇关于KMP算法的笔记而绘制的图示。
作者其他创作
大纲/内容
P a c b a c b c
P a c b a c b c
b.P右移3位,匹配成功
a.匹配失败,需要右移P
P整体右移3位,有效位移
T a b a c a a c a a c a c b a c c b
P a c b a c b c
T a b a c b a c b a c b c b a c c b
P a c b a c b c
P a c b a c b c
c.P右移5位,匹配失败
s'=s+3
P a c b a c b c
P a c b a c b c
P整体右移2位,无效位移
(4)P整体右移1位,s=3;T[3+1]!=P[1],匹配失败
(3)P整体右移1位,s=2;T[2+j]=P[j](j=1...6), T[2+7]!=P[7],匹配失败
(1)P和T左对齐,s=0;T[1]=P[1],T[2]!=P[2]匹配失败
s'=s+1
P a c a a c a c
s=5
s'=s+2
P a c a a c a c
P a c a a c a c
P整体右移1位,无效位移
多组相同的前后缀情况
(2)P整体右移1位,s=1;T[1+1]!=P[1],匹配失败
0 条评论
回复 删除
下一页