字符串匹配过程图示
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 条评论
回复 删除
下一页
