《KMP字符串模式匹配算法》教学课例
程玉胜
安庆师范学院计算机与信息学院
KMP字符串模式匹配是数据结构课程中一个重要的知识点也是一个难点学过KMP算法的同学100认为KMP是数据结构课程中最难的部分。为了消除他们对KMP算法学习的恐惧心理激发他们的学习兴趣调动其积极性显得尤为重要。
基于以上我们根据学生的认知特点和接受水平对教材内容进行了重新构建并按照数据结构中“时间复杂度”概念增加了不同模式匹配算法的运行时间动态逼真的显示了算法的“时间”性能获得了较好的教学效果。
一、教学目标
知识目标让学生了解KMP算法应用的普遍性。如在目前众多的文字处理软件中得到广泛应用如MicrosoftWord中的“查找”或“替换”操作。而这种操作实现的机制同学们特别是计算机专业的学生很少去想过。
能力目标要求学生体验一个完整的抽象数据类型ADT的实现方法和过程并学会判断、计算算法优劣的方法。
价值目标消除恐怖的学习心态让学生感悟数据结构算法实际应用价值从而激发学习的兴趣形成积极主动式学习的态度。
二、教材分析
使用教材是清华大学严蔚敏教授并由清华大学出版社出版的《数据结构C语言版》该教材难度较大其实验方法特别是ADT方法在教材中介绍较少而且KMP算法更是从
f理论分析的角度介绍了匹配算法和
ext的计算自学难度很大虽然该节知识点属于“表示难度较大可以不讲”但是其又是考研的一个热点所以我们又不得不讲。
三、教学重点、难点
教学重点KMP算法中的
ext和改进的
extval计算
教学难点KMP算法中如何计算
ext值
四、教具准备
卡片多个字符串字符串指针
强力磁吸6个
五、互动式教学过程
教学
内容
教师活动学生活动目标状态
创设情境引入课题
目前的众多软件中“查
找”、“替换”等操作实现
方法要求学生举例。
给出一篇word文档
完成在上述文档中从当前位置向后查找
“计算机”或者向前查找“计算机”字符串
的方法。
这些软件中“查找”操作是
怎么实现的
提出问题
教师给出如下任务手
动演示如下两个字符串的查
找操作。
例如在串S”
abcabcabdabba”中查找T”
abcabd”的位置。
学生分组讨论演示“查找”过程如图
教具演示
我们发现比较到S6和T6不
等时怎么办
解决问题简单匹配算法引入“简单匹配算法”
给出上例的匹配过程前两
步
第一趟、
第二趟、
学生完成匹配后面过程
第三趟、
第四趟、
要求学生计算匹配次数通过4次匹配
终于在S串中“查找”到T串位置时4
在第一趟比较后进行的第
二趟、第三趟比较有必要吗
f进一步提出问题
r