实验四：KMP算法实验报告
一、问题描述
模式匹配两个串。
二、设计思想
这种由DEK
uthJHMorris和VRPratt同时发现的改进的模式匹配算法简称为KMP算法。
注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：
i
tI
dexStri
gSStri
gTi
tpos参考《数据结构》中的程序
iposj1这里的串的第1个元素下标是1whileiSLe
gthjTLe
gth
ifSiTjijelseiij2j11ifjTLe
gthretur
iTLe
gth匹配成功elseretur
0匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子：SaaaaabababcaaaTababcaaaaabababcaaaababc表示前一个已经失配回溯的结果就是aaaaabababcaaa
ababc如果不回溯就是aaaaabababcaaa
ababc这样就漏了一个可能匹配成功的情况aaaaabababcaaa
ababc这是由T串本身的性质决定的，是因为T串本身有前后部分匹配的性质。如果T为abcdef这样的，大没有回溯的必要。改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：
fababdababcababc
这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当Tj失配后，j应该往前跳的值就是j的
ext值，它是由T串本身固有决定的，与S串无关。
《数据结构》上给了
ext值的定义：0如果j1
extjMaxk1kj且p1pk1pjk1pj11其它情况
其实它就是描述前面表述的情况，关于
ext10是规定的，这样规定可以使程序简单一些，如果非要定为其它的值只要不和后面的值冲突也是可以的；而那个Max是什么意思，举个例子：
Taaabaaaab
aaabaaab
aaabaaab
像这样的T，前面自身部分匹配的部分不止两个，那应该往前跳到第几个呢？最近的一个，也就是说尽可能的向右滑移最短的长度。
到这里，就实现了KMP的大部分内容，然后关键的问题是如何求
ext值？先看如何用它来进行匹配操作。
将最前面的程序改写成：i
tI
dex_KMPStri
gSStri
gTi
tpos
iposj1这里的串的第1个元素下标是1whileiSLe
gthjTLe
gth
ifj0SiTjij注意到这里的j0和j的作用就知道为什么规定
ext10的好处了
elsej
extji不变（不回溯）j跳动ifjTLe
gthretur
iTLe
gth匹配成功elseretur
0求
ext值，这也是整个算法成功的关键r