《KMP字符串模式匹配算法》教学课例

1、KMP字符串模式匹配算法教学课例程玉胜安庆师范学院计算机与信息学院KMP字符串模式匹配是数据结构课程中一个重要的知识点，也是一个难点（学过KMP算法的同学100%认为:KMP是数据结构课程中最难的部分）。为了消除他们对KMP算法学习的恐惧心理，激发他们的学习兴趣，调动其积极性，显得尤为重要。基于以上，我们根据学生的认知特点和接受水平，对教材内容进行了重新构建，并按照数据结构中“时间复杂度”概念，增加了不同模式匹配算法的运行时间，动态逼真的显示了算法的“时间”性能，获得了较好的教学效果。一、教学目标知识目标：让学生了解KMP算法应用的普遍性。如：在目前众多的文字处理软件中得到广泛应用,如Micr

2、osoftWord中的查找”或替换”操作。而这种操作实现的机制,同学们特别是计算机专业的学生很少去想过。能力目标:要求学生体验一个完整的抽象数据类型（ADT）的实现方法和过程,并学会判断、计算算法优劣的方法。价值目标：消除恐怖的学习心态，让学生感悟数据结构算法实际应用价值，从而激发学习的兴趣，形成积极主动式学习的态度。二、教材分析使用教材是清华大学严蔚敏教授并由清华大学出版社出版的数据结构（C语言版）,该教材难度较大，其实验方法特别是ADT方法在教材中介绍较少,而且KMP算法更是从理论分析的角度介绍了匹配算法和next的计算，自学难度很大；虽然该节知识点属于“*（表示难度较大，可以不讲），但是

3、其又是考研的一个热点，所以我们又不得不讲。三、教学重点、难点教学重点：KMP算法中的next和改进的nextval计算教学难点：KMP算法中如何计算next值四、教具准备卡片：多个字符串，字符串指针强力磁吸：6个五、互动式教学过程教学内容教师活动学生活动目标状态创设情境引入课题目前的众多软件中，查找、替换等操作实现方法，要求学生举例。给出一篇word文档完成在上述文档中从当前位置向后查找计算机或者向前查找计算机字符串的方法。这些软件中查找操作是怎么实现的？教师给出如下任务：手学生分组讨论，演示查找过程，如图动演示如下两个字符串的查（教具演示）提出找操作。问题例如：在串S=”abcabcabda

4、bba中查找T=abcabd的位置。引入简单匹配算法给出上例的匹配过程前两学生完成匹配后面过程第三趟、我们发现比较到S6和T不等时，怎么办？解决问题第一趟、I简单第四趟、在第一趟比较后，进行的第二趟、第三趟比较有必要吗？匹配算法第二趟、要求学生计算匹配次数通过4次匹配,终于在S串中查找至T串，位置时！第一趟后，当S6HT6时，第二趟进行S2与T进一比较是必要的吗？步提第三趟进行S与T1出问比较是必要的吗？题第四趟进行S4与T1比较是必要的吗？第四趟进行S4与T2比较是必要的吗？引入MP匹配算法”解决第一趟，当S6/T6时，问题S下标不是回溯到2,T下标|也不是回溯到开始，而是根KMP据T中T6

5、=d的模式匹配函数值(next6=3，为什么？算法后面讲)进行匹配，要求学生完成匹配过程教学重点内容弓I入模式值nextn啲I计算next定义：略值的计算第一趟：学生讨论，然后找学生提问，最后证明。当S6/T6时，根据next6=3匹配过程：ai14set3ap31u要求学生计算匹配次数：仅通过2次匹配，终于在S串中查找”到T串，位置时4下标12345Tabcabnext01112例二、求T=abcab的模式函数的值。学生完成后面的工作:当出现S5/T5时，根问题据next5=2,得：的进第二趟、一步提出第三趟、要求学生计算匹配次数:仅通过5次匹配，在S串中查找”到T串，位置时7如果是不必要的

6、，那么第一趟后，当S6/T6时，S与T比较是必要的呢！“”怎么求？next6=3含义：其实这个3表示T=d的前面有2个字符和开始的两个字符相同怎么求串的模式值nextn？设T=“abcab”,S二abcadcabcab，利用KMP算法进行匹配，几次匹配成功？存在什么问题？比如：abcab模式串中，NEXT值为(01112)。当比较到T5=b不成功时，原NEXT的值跟T2比较可事实上丁2也是b,与T5相同，所以可以直接跟T1比较。可见，第二趟比较是多余的，那么如何改进呢？教学nextn改进为要求学生计算nextval值完成理论教学目标，那么在重点nextvaln:下标12345计算机中我们怎样编

7、程实现？内容如果Tj/Tk,Tabcac另外几种算法的时间复杂度怎|k=nextj否则k=nextknext01112样计算？nextval值的计算nextval0根据nextval，计算改进后的匹配次数。成品介绍|ADT简单匹配算法主动式学习与模仿IKMP算法实现演示：简单匹配算法介绍抽象数据类型的简单匹配算法实现及其时间复杂度计算方法。教师辅导1.给出字符串abacabaaad在KMP算法中的next和课堂作业nextval数组。2对S=aabcbabcaabcaaba,T=bca，画出T为模式串，S为目标串的匹配过程。提咼创新仿照WORD文档中的查找操作，编程实现在文本文件中查找指定的字

8、符串位置。课堂作业、课后作业答案将在数据结构在线学习网站一网站公告中公布网上答疑附：详细的教学过程进一步认识数据封装的含义，在原有程序基础上增加“匹配次数的计算方法结果：学生模仿简单匹配算法实现代码，实现KMP算法程序调试过程时，学生可以向下面的学生求助，也可以向老师求助10分钟完成，并检查掌握情况学生讨论，查找相关文献资料在学习过程中遇到的不懂的、或者难题,请同学继续在数据结构在线学习网站一网上答疑中提交怎样实现KMP算法及其改进的模式匹配算法进一步熟悉了ADT编程方法和调试机巧课后作业：求串ababaaababaa的next函数值。模式串t=abcaabbcaabdab,求模式串的next

9、和nextval函数的值。将结果上传至作业存储的ftp服务器 HYPERLINK 4949对于网上答疑中的问题,我们将及时回复，目前网上答疑的开通,极大的方便了老师与学生的交流，反映效果较好。1、创设情境，引入课题老师：目前的众多软件中,查找”、替换”等操作实现方法，要求学生举例。给出篇word文档学生:完成在上述文档中从当前位置向后查找计算机”或者向前查找计算机”字符串的方法。2、提出问题，解决问题老师：这些软件中“查找”操作是怎么实现的？教师给出如下任务手动演示如下两个字符串的查找操作例如在串S=abcabcabdabba”中查找T=”abcabd的位置。学生分组讨论，演示“查找”过程，如

10、图1（教具演示）12345678910111213abcatIcabdabbao.,r.-v-1zVabcabid123456老师提出问题：我们发现比较到S6和T不等时，怎么办？解决问题：引入“简单匹配算法”3、简单匹配算法基本的模式匹配算法:以主串的某个字符与子串的第一个字符相比较,若相等,则继续比较二者的后一个字符，否则主串的字符指针从开始与子串第一个字符比较处后移一个位置，而子串的字符指针重新指向子串的第一个字符。当这样一个失配发生时，T下标必须回溯至I开始,S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：12345百了呂910口U13S|糾b#|糾b|c忸|b|MI規|b

11、|b|刃|帀abca1bdo123456这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标4。如图：上述通过4次匹配，终于在S串中查找”到T串，位置时4。老师再次提出问题：在第一趟比较后，进行的第二趟、第三趟比较有必要吗？提问的形式：让学生讨论如下问题，第一趟后，当S6HT6时,第二趟进行S与T1比较是必要的吗？第三趟进行S3与T1比较是必要的吗？第四趟进行S4与T1比较是必要的吗？第四趟进行S4与T比较是必要的吗？如果是不必要的，那么

12、第一趟后，当S6HT6时，S6与T?比较是必要的呢!解决问题：引入“KMP匹配算法”4、KMP匹配算法KMP算法：KMP算法是对传统模式匹配算法的较大改进，在传统的模式匹配算法中，当出现主串中的字符与子串中的字符不等时同时向前回溯了两个指针，一个是主串的指针,一个是子串的指针。而KMP算法的基本思路是在不回溯主串的指针，而只回溯子串的指针的情况下完成模式匹配，这样就省去了回溯主串指针进行比较的一部分时间。KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。还是相同的例子，在S=abcabcabdabba”中查找T=”abcabd，如果使用KMP匹配算法，当第一次搜索到S6和T

13、6不等后，S下标不是回溯到2,T下标也不是回溯到开始，而是根据T中T6=d的模式函数值（next6=3，为什么？后面讲），直接比交S6和T是否相等，因为相等,S和T的下标同时增加;因为又相等，S和T的下标又同时增加。最终在S中找到了T。如图：next6=3含义:其实这个3表示T6=d的前面有2个字符和开始的两个字符相同。abcibcab|d|abba个-.|rabcatdo1234567891011121312S456请看图：因为，S5=T，S4=T4，根据next6=3，有T4=T1，T5=T2，所以S4=T1，S=T2（两对相当于间接比较过了），因此，接下来比较S6和T是否相等。有人可能会

14、问：S4和T1,S5和T2是根据next6=3间接比较相等，那S2和T1,S3和T1之间又是怎么跳过,可以不比较呢?因为S1=T1,S2=T2,S3=T3,而T1!=T2,T2!=T3,=S1!=S2,S2!=S3,所以S2!=T1,S3!=T1.还是从理论上间接比较了。5.怎么求串的模式值nextn定义：0如果j=1nextj=Maxkllvkvj且p1.pk-1=pj-k+1.pj-11其它情况（1）next1=0意义：任何串的第一个字符的模式值规定为0。（2）nextj=k意义:模式串T中下标为j的字符，如果j的前面k-1个字符与开头的k-1个字符相等，即：T1T2.Tk-1=Tj-k+

15、1Tj-k+2.Tj-1（3）nextj=1其他情况。例1）求T=“abcac”的模式函数的值。标下12345Tabcactnex01112例2)求T=”ababcaabc”的模式函数的值。下标12345678TabCabCadnext01112345课后题：求T=”ababcabababc”的模式函数的值。6.nextn不足与改进：KMP的改进算法主要是针对求NEXT数组的算法思想进行的改进。数组的效率，引入了NEXTVAL数组(即NEXT的改进值)。NEXTVAL避比如：abcdabce”模式串中，NEXT,NEXTVAL值为(01110114)。当比较到T7=C不成功时，原NEXTT3也

16、是C，与T7相同，所以可以直接跟T1比较。举例：若T=abcab”的模式函数的值下12345标Tabcabnex01112t若S二“abcadcabcab”，12345678910li12salbCadCabCab0abeNbho12345nextn改进为nextvaln:如果Tj!=Tk，k=nextj否则k=nextk下12345标Tabcabnex01101t1234567呂9101112釦b|糾d|c|刃|b|c|辺|b|oabebho12345练习：求T=AAAAAAAAAAB的模式函数值，并用后面的求模式函数值函数验证。7.nextn意义：设在字符串S中查找模式串T,若Sm!=Tn

17、,那么，取Tn的模式函数值nextn,(1)、nextn=0表示Sm和T1间接比较过了，不相等，下一次比较Sm+1和T1、nextn=1表示比较过程中产生了不相等，下一次比较Sm和T1。、nextn=k表示Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk相等吗？、其他值，不可能。课后习题：求串ababaaababaa的next函数值。模式串t=abcaabbcaabdab，求模式串的next和nextval函数的值。给出字符串abacabaaad在KMP算法中的next和nextval数组。S=aabcbabcaabcaaba，T=bca，画出以T为模式串，S为目标串的匹配过程。习题答案：求串ababaaababaa的next函数值。【解答】j123456789101112串ababaaababaanextj011234223456模式串t=abcaabbcaabdab，求模式串的next和nextval函数