主串和模式串的长度if（j0）or（sipi）the
begi

fii1；jj1；继续下一对字符的比较e
delsej
extj；模式串向右滑动ifjple
gththe
KMPiple
gth匹配成功elseKMP0；e
d；（五）求
ext数组的算法从上述讨论已知，
ext数组的值仅与模式串本身有关，而与相匹配的主串无关，我们可以根据模式串，从分析其定义出发，用递推的方法求得
ext数组的值。由定义知：
ext10设已求得
extjk，求
extj1有两种情况：1．若PkPj，则表明在模式串中：P1Pk＝Pjk1Pj就是说
extj1k1，即：
extj1
extj12．若Pk≠Pj，则表明在模式串中：P1Pk≠Pjk1Pj此时如何处理？procedure
extvarijk：i
tegerbegi
ext10；k0；forj1top_le
gth1dobegi

p_le
gth为模式串P的长度
if（k0）or（PjPk）the
begi

else
e
dbegi

e
d；e
d；e
d；参考答案：①kk1；
extj1k；②repeatk
extk；
fu
til（k0）or（PjPk）；kk1；
extj1k；求
ext数组程序2：procedure
ext；varjk：i
teger；begi
j1；k0；
ext10；whilejp_le
gthdoif（k0）or（PjPk）the
begi
jj1；kk1；
extjk；e
delsek
extk；e
d；另一种求
ext数组的算法：procedure
ext；readl
p；
ext10；forj2top_le
gthdobegi
kj1；repeatkk1；u
tilcopyp1kcopypjkk；
extjk1；e
d；e
d；（六）进一步优化：前面定义的
ext函数在某些情况下尚有缺陷，例如：模式串Paaaab和主串Saaabaaaab匹配当i4，j4，S4≠P4时，由
extj的指示，模式串向右移，S4还要与P3、P2、P1继续比较。实际上，因为模式串中第1、2、3个字符和第4个字符都相等，没必要再和S4相比较，可将模式串直接向右滑动4个字符，进行i5、j1时的比较。为了克服这种不必要的重复比较，对求
ext的算法进行改进，其基本思想是：在求得j点的k值后，在判断Pk和Pj是否相等，若相等则把
extvalk值送
extvalj中，否则把原来的k值存入
extvalj中。表中的
extvalj就是改进后的值。j
f1234567891011模式串Pabcabcabb
extj011123456
extvalj011011016ac
1202
算法为：procedure
ext2；varjk：i
teger；begi
j1；k0；
extval10；whilejp_le
gthdoif（k0）or（PjPk）the
begi
jj1；kk1；ifPjPkthe
extvalj
extvalkelse
extvaljk；e
delsek
extvalk；e
d；
§413串的BM匹配算法在实际的模式匹配中，往往失配的机会反而比匹配的机会要多，针对这种r