← 演示目录

KMP 匹配

全书 04

严 1 下标。P=abaabc,next=0 1 1 2 2 3(next[1]=0)。主串 T=abaabaabaabc。失配 j ← next[j],i 不动;匹配则 i、j 同增。j=0 时下一次把 i 推进一步并令 j=1。本串第一次命中起点 i=7(1 下标)。

STEP 0
READYi=1, j=1 对准 T 与 P 的首字符。