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

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

程玉胜

安庆师范学院计算机与信息学院

KMP字符串模式匹配是数据结构课程中一个重要的知识点，也是一个难点（学过KMP算法的同学100％认为:KMP是数据结构课程中最难的部分）。为了消除他们对KMP算法学习的恐惧心理，激发他们的学习兴趣，调动其积极性，显得尤为重要。

基于以上，我们根据学生的认知特点和接受水平，对教材内容进行了重新构建，并按照数据结构中?时间复杂度?概念，增加了不同模式匹配算法的运行时间，动态逼真的显示了算法的?时间?性能，获得了较好的教学效果。

一、 教学目标

知识目标：让学生了解KMP算法应用的普遍性。如：在目前众多的文字处理软件中得到广泛应用，如Microsoft Word中的?查找?或?替换?操作。而这种操作实现的机制，同学们特别是计算机专业的学生很少去想过。

能力目标：要求学生体验一个完整的抽象数据类型（ADT）的实现方法和过程，并学会判断、计算算法优劣的方法。

价值目标：消除恐怖的学习心态，让学生感悟数据结构算法实际应用价值，从而激发学习的兴趣，形成积极主动式学习的态度。

二、 教材分析

使用教材是清华大学严蔚敏教授并由清华大学出版社出版的《数据结构（C语言版）》，该教材难度较大，其实验方法特别是ADT方法在教材中介绍较少，而且KMP算法更是从理论分析的角度介绍了匹配算法和next的计算，自学难度很大；虽然该节知识点属于?**（表示难度较大，可以不讲）?，但是其又是考研的一个热点，所以我们又不得不讲。

三、 教学重点、难点

教学重点：KMP算法中的next和改进的nextval计算 教学难点：KMP算法中如何计算next值

四、 教具准备

卡 片：多个字符串，字符串指针 强力磁吸：6个

五、 互动式教学过程

教学内容 创设情境引入课题 提出问题 教师活动 目前的众多软件中，?查找?、?替换?等操作实现方法，要求学生举例。 给出一篇word文档 教师给出如下任务：手动演示如下两个字符串的查找操作。 学生活动 目标状态 完成在上述文档中从当前位置向后查找?计算机?或者向前查找?计算机?字符串的方法。 这些软件中?查找?操作是怎么实现的？ 学生分组讨论，演示?查找?过程，如图（教具演示） 我们发现比较到S[6] 和T[6]不等时，怎么办？ 例如：在串abcabd?的位置。 S=?abcabcabdabba?中查找T=? 引入?简单匹配算法? 给出上例的匹配过程前两步： 解决问题 | 简单匹配算法 第一趟后，当S[6]≠T[6]时， ? 进一步提出问题 ? ? ? 第二趟进行S[2]与T[1]比较是必要的吗？ 第三趟进行S[3]与T[1]比较是必要的吗？ 第四趟进行S[4]与T[1]比较是必要的吗？ 第四趟进行S[4]与T[2]比较是必要的吗？ 引入?MP匹配算法? 解决问题 | KMP匹配算法 第一趟，当S[6]≠T[6]时， S下标不是回溯到2，T下标也不是回溯到开始，而是根据T中T[6]==’d’的模式函数值（next[6]=3，为什么？后面讲）进行匹配，要求学生完成匹配过程 教学重点内容 | next值的计算 问题的进第一趟： 学生完成后面的工作： 比如：?abcab?模式串中，NEXT值为(0 1 1 1 2 )。当比较引入?模式值next[n]的计算? 定义 ：略 学生完成匹配后面过程 第三趟、 第一趟、 第二趟、 要求学生计算匹配次数：通过4次匹配，终于在S串中?查找?到T串，位置时4 第四趟、 在第一趟比较后，进行的第二趟、第三趟比较有必要吗？ 如果是不必要的，那么第一学生讨论，然后找学生提问，最后证明。 趟后，当S[6]≠T[6]时， S[6]与T[ ？]比较是必要的呢！?？?怎么求？ 当S[6]≠T[6]时，根据next[6]=3匹配过程： next[6]=3含义： 其实这个3表示T[6]==’d’的前面有2个字符和开始的两 要求学生计算匹配次数：仅通过2次匹配，终于在S串中?查找?到T串，位置时4 个字符相同? 怎么求串的模式值 next[n]？ 例二、求T=?abcab?的模式函数的值。 下标 T next 1 a 0 2 b 1 3 c 1 4 a 1 5 b 2 设T=?abcab?，S＝?abcadcabcab?，利用KMP算法进行匹配，几次匹配成功？存在什么问题？ 一步提出 当出现S[5]≠T[5]时，根据next[5]=2,得： 第二趟、 要求学生计算匹配次数：仅通过5次匹配，在S串中?查找?到T串，位置时7 第三趟、 到T[5]=b不成功时，原NEXT的值跟T[2]比较，可事实上，T[2]也是b，与T[5]相同，所以可以直接跟T[1]比较。 可见，第二趟比较是多余的，那么如何改进呢？ 教学重点内容 | nextval值的要求学生计算nextval值 next[n] nextval[n]： 如果T[j]≠T[k]，k=next[j] 否则k=next[k] 演示：简单匹配算法 改进为下标 T next nextval 1 a 0 0 2 b 1 ? 3 c 1 ? 4 a 1 ? 5 c 2 ? 完成理论教学目标，那么在计算机中我们怎样编程实现？另外几种算法的时间复杂度怎样计算？ 计算 根据nextval，计算改进后的匹配次数。 成品介绍 | ADT 简单匹配算法 介绍抽象数据类型的简单匹配算法实现及其时间复杂度计算方法。 主动式学习与模仿 | KMP 算法实现 1. 给出字符串‘abacabaaad’在KMP算法中的next和课堂作业 nextval数组。 2．对S=’aabcbabcaabcaaba’，T=’bca’，画出T为模式串，S为目标串的匹配过程。 教师辅导 进一步认识?数据封装?的含义，在原有程序基础上增加?匹配次数?的计算方法: 结果： 怎样实现KMP算法及其改进的模式匹配算法 学生模仿?简单匹配算法?实现代码，实现?KMP算法? 程序调试过程时，学生可以向下面的学生求助，也可以向老师求助 进一步熟悉了ADT编程方法和调试机巧 课后作业： 1．求串’ababaaababaa’ 的next10分钟完成，并检查掌握情况 函数值。 2模式串t=’abcaabbcaabdab’，求模式串的next和nextval函数的值。 仿照WORD文档中的提高创新 ?查找?操作，编程实现在文本文件中查找指定的字符串位置。 课堂作业、课后作业答案将在数据结构在线学习网站—网站公告?中公布 网上答疑 在学习过程中遇到的不懂的、或者难题，请同学继续在?数据结构在线学习网站—网上答疑?中提交 学生讨论，查找相关文献资料 将结果上传至作业存储的ftp服务器 ftp://219.231.49.249 对于?网上答疑?中的问题，我们将及时回复，目前?网上答疑?的开通，极大的方便了老师与学生的交流，反映效果较好。

附：详细的教学过程

1、创设情境，引入课题

老师：目前的众多软件中，?查找?、?替换?等操作实现方法，要求学生举例。给出一篇word文档

学生：完成在上述文档中从当前位置向后查找?计算机?或者向前查找?计算机?字符串的方法。

2、提出问题，解决问题

老师：这些软件中?查找?操作是怎么实现的？ 教师给出如下任务：手动演示如下两个字符串的查找操作，例如：在串S=?abcabcabdabba?中查找T=? abcabd?的位置。

学生分组讨论，演示?查找?过程，如图1（教具演示）

老师提出问题：我们发现比较到S[6] 和T[6]不等时，怎么办？ 解决问题：引入?简单匹配算法? 3、 简单匹配算法

基本的模式匹配算法：以主串的某个字符与子串的第一个字符相比较，若相等，则继续比较二者的后一个字符，否则主串的字符指针从开始与子串第一个字符比较处后移一个位置，而子串的字符指针重新指向子串的第一个字符。

当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：