反之,着在(4-1)所示的状态下,模式p中p之前存 在长度为-1的真前缀和真后缀的匹配,即[p-p 2]=[p1-p1且p:=p1当p与t出现不等时,根据 前面已比较的结果p1=t+1,P2=t+2,…p1=t 1,于是可得p=t+1,p1=tk p2=t1,因 此接下来只需从p1与t开始继续后继对应字符的比较 即可。 再假设在(4-1)所示的状态下,模式右移一位成为 状态(4-2)后,匹配仍然不成功,说明[P0P2 ≠[p1p;1p:=p,于是模式再右移一位,成为状 态(4-3),若此次匹配成功,仿照上述分析,必有 Po p1 p 。。●● Pi-3 Pi-2 Pi-1 P反之，若在(4-1)所示的状态下，模式p中pi之前存 在长度为i-1的真前缀和真后缀的匹配，即[p0—pi- 2 ]=[p1—pi-1 ] 且pi-1≠pi；当pi与tr出现不等时，根据 前面已比较的结果p1= tk+1，p2= tk+2，……pi-1= tr- 1，于是可得p0= tk+1，p1= tk+2，……pi-2= tr-1，因 此接下来只需从pi-1与tr开始继续后继对应字符的比较 即可。 再假设在(4-1)所示的状态下，模式右移一位成为 状态(4-2)后，匹配仍然不成功，说明[p0—pi-2 ] [p1—pi-1 ]或pi-1=pi，于是模式再右移一位，成为状 态(4-3)，若此次匹配成功，仿照上述分析，必有： p0 p1 p2…… pi-3 pi-2 pi-1 pi………