院系：班级：姓名：学号：指导教师：
计算机科学技术学院软件112张萌20111702010235贺薪宇
2013年11月10日
f摘
要
KMP算法对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会
发生退化，是一个非常优秀的模式匹配算法。但是由于KMP算法在构造跳转表
ext过程中进行了多个层面的优化和抽象，使得KMP算法进行模式匹配的原理较难理解。本文能够深入KMP算法，分析算法各个细节。
关键词
KMP算法模式函数值
ext数组
f目
录
1程序的功能设计错误！未定义书签。2程序的数据设计错误！未定义书签。3程序的函数设计错误！未定义书签。4函数编程及调试错误！未定义书签。5整体调试错误！未定义书签。6总结错误！未定义书签。参考文献错误！未定义书签。致谢1
1
f1背景
Cook于1970年证明的一个理论得到，任何一个可以使用被称为下推自动机的计算机抽象模型来解决的问题，也可以使用一个实际的计算机（更精确的说，使用一个随机存取机）在与问题规模对应的时间内解决。特别地，这个理论暗示存在着一个算法可以在大约m
的时间内解决模式匹配问题，这里m和
分别是存储文本和模式串数组的最大索引。K
uth和Pratt努力地重建了Cook的证明，由此创建了这个模式匹配算法。大概是同一时间，Morris在考虑设计一个文本编辑器的实际问题的过程中创建了差不多是同样的算法。这个算法就是KMP算法。kmp算法是一种改进的字符串匹配算法，由DEK
uth与VRPratt和JHMorris同时发现，因此人们称它为克努特莫里斯普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1m定义一个
ext函数。
ext函数包含了模式串本身局部匹配的信息。
2基本思想
KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。假设在模式匹配的进程中，执行Ti和Wj的匹配检查。若TiWj，则继续检查Ti1和Wj1是否匹配。若Ti不等于Wj，则分成两种情况：若j1，则模式串右移一位，检查Ti1和W1是否匹配；若1jm，则模式串右移j
ext（j）位，检查Ti和W
extj是否匹配。重复此过程直到jm或i
结束。
3简单匹配算法（BF算法）
在介绍KMP算法之前，先介绍一下BF算法。
31BF算法定义
BF算法r