被进一步优化的。
61优化过程
我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示：下标ipi
exti0a11b02c03d04a05a16b17c28a39b1
但是，如果此时发现pipk）那么应当将相应的
exti的值更改为
extk，的值。经过优化后可以得到下面的表格：
7
f下标ipi
exti优化的
exti
0a11
1b00
2c00
3d00
4a01
5a11
6b10
7c20
8a33
9b10
62优化后
ext
的意义
（1）
ext01意义：任何串的第一个字符的模式值规定为1。（2）
extj1意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k个字符不等（或者相等但TkTj）（1≤kj）。如：T”abCabCad”则
ext61，因T3T6（3）
extjk意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且TjTk（1≤kj）。即T0T1T2。。。Tk1TjkTjk1Tjk2Tj1且TjTk（1≤kj）4
extj0意义：除（1）（2）（3）的其他情况。
63优化后
ext的代码实现
voidgetNextco
stcharpatter
i
t
ext
ext01i
tk1j0whilepatter
j0whilek1patter
kpatter
jk
extkjkifpatter
kpatter
j
extj
extkelse
extjk
8
f致
谢
在这次课程设计的撰写过程中，我得到了许多人的帮助。首先，我要感谢贺薪宇老师在课程设计上给予我的指导、提供给我的支持和帮助，这是我能顺利完成这次报告的主要原因，更重要的是贺老师帮我解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力。贺老师严谨求实的治学态度，踏实坚韧的工作精神，将使我终生受益。再多华丽的言语也显苍白。在此，谨向贺老师致以诚挚的谢意和崇高的敬意其次，我要感谢帮助过我的同学，特别是我的舍友，他们也为我解决了不少我不太明白的设计难题。同时也感谢学院为我提供良好的做课程设计的环境。最后，再一次感谢所有在设计中曾经帮助过我的良师益友和同学。
1
fr