第一趟后当S6≠T6
时
◆第二趟进行S2与T1
比较是必要的吗
◆第三趟进行S3与T1
比较是必要的吗
◆第四趟进行S4与T1
比较是必要的吗
◆第四趟进行S4与T2
比较是必要的吗
学生讨论然后找学生提问最后证明。
如果是不必要的那么第一
趟后当S6≠T6时
S6与T比较是必要
的呢“”怎么求
解决问题KMP匹配算法
引入“MP匹配算法”
第一趟当S6≠T6时
S下标不是回溯到2T下标
也不是回溯到开始而是根
据T中T6’d’的模式
函数值
ext63为什么
后面讲进行匹配要求学
生完成匹配过程
当S6≠T6时根据
ext63匹配过程
要求学生计算匹配次数仅通过2次匹
配终于在S串中“查找”到T串位置时
4
ext63含义
其实这个3表示T6’d’
的前面有2个字符和开始的两个
字符相同”
怎么求串的模式值
ext
教学重点
内容
ext值的计算
引入“模式值
ext
的
计算”
定义略
例二、求T“abcab”的模式函数的值。
下标12345
Tabcab
ext01112
设T“abcab”S
“abcadcabcab”利用KMP算
法进行匹配几次匹配成功存
在什么问题
问题的进一步提出第一趟
当出现S5≠T5时根
据
ext52得
第二趟、
第三趟、
学生完成后面的工作
要求学生计算匹配次数仅通过5次匹
配在S串中“查找”到T串位置时7
比如“abcab”模式串中
NEXT值为01112。当比较
到T5b不成功时原NEXT
的值跟T2比较可事实上T2
也是b与T5相同所以可以
直接跟T1比较。
可见第二趟比较是多余的
那么如何改进呢
教学重点内容
ext
改进为
extval
如果Tj≠Tk
k
extj否则k
extk
要求学生计算
extval值
下标12345
Tabcac
ext01112
完成理论教学目标那么在
计算机中我们怎样编程实现
另外几种算法的时间复杂度怎
样计算
f
extval值的计算
extval0根据
extval计算改进后的匹配次数。
成品介绍ADT简单匹配算法演示简单匹配算法
介绍抽象数据类型的简单匹
配算法实现及其时间复杂度
计算方法。
进一步认识“数据封装”的含义在原有
程序基础上增加“匹配次数”的计算方法
结果
怎样实现KMP算法及其改
进的模式匹配算法
主动式学习与
模仿KMP算法实现教师辅导
学生模仿“简单匹配算法”实现代码实
现“KMP算法”
程序调试过程时学生可以向下面的学生
求助也可以向老师求助
进一步熟悉了ADT编程方
法和调试机巧
课堂作业1给出字符串‘abacabaaad’
在KMP算法中的
ext和
extval数组。
2对S’aabcbabcaabcaaba’
T’bca’画出T为模式
串S为目标串的匹配过程。
10分钟完成并检查掌握r