情况
课后作业
1求串’ababaaababaa’的
ext
函数值。
2模式串t’abcaabbcaabdab’
求模式串的
ext和
extval函数
的值。
提高创新
仿照WORD文档中的
“查找”操作编程实现在
文本文件中查找指定的字符
串位置。
学生讨论查找相关文献资料
将结果上传至作业存储的
ftp服务器
ftp21923149249
网上答疑
课堂作业、课后作业答
案将在数据结构在线学习网
站网站公告”中公布
在学习过程中遇到的不懂的、或者难题
请同学继续在“数据结构在线学习网站网
上答疑”中提交对于“网上答疑”中的问题
我们将及时回复目前“网上答
疑”的开通极大的方便了老师
与学生的交流反映效果较好。
附详细的教学过程
f1、创设情境引入课题
老师目前的众多软件中“查找”、“替换”等操作实现方法要求学生举例。给出一篇word文档
学生完成在上述文档中从当前位置向后查找“计算机”或者向前查找“计算机”字符串的方法。
2、提出问题解决问题
老师这些软件中“查找”操作是怎么实现的
教师给出如下任务手动演示如下两个字符串的查找操作例如在串S”abcabcabdabba”中查找T”abcabd”的位置。
学生分组讨论演示“查找”过程如图1教具演示
老师提出问题我们发现比较到S6和T6不等时怎么办
解决问题引入“简单匹配算法”
3、简单匹配算法
基本的模式匹配算法以主串的某个字符与子串的第一个字符相比较若相等则继续比较二者的后一个字符否则主串的字符指针从开始与子串第一个字符比较处后移一个位置而子串的字符指针重新指向子串的第一个字符。
当这样一个失配发生时T下标必须回溯到开始S下标回溯的长度与T相同然后S下标增1然后再次比较。如图
f这次立刻发生了失配T下标又回溯到开始S下标增1然后再次比较。如图
又一次发生了失配所以T下标又回溯到开始S下标增1然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标4。如图
上述通过4次匹配终于在S串中“查找”到T串位置时4。
老师再次提出问题在第一趟比较后进行的第二趟、第三趟比较有必要吗
提问的形式让学生讨论如下问题
第一趟后当S6≠T6时
第二趟进行S2与T1比较是必要的吗
第三趟进行S3与T1比较是必要的吗
第四趟进行S4与T1比较是必要的吗
第四趟进行S4与T2比较是必要的吗
f如果是不必要的那么第一趟后当S6≠T6时
S6与T比较是必要的呢
解决问题引入“KMP匹配算法”
4、KMP匹配算法
KMP算法KMP算法是对传统模式匹配算法的较大改进在传统的模式匹配算法中当出现主串中的字符与子串中的r