1、6个五、互动式教学过程教学内容教师活动学生活动目标状态创设情境引入课题目前的众多软件中，“查找”、“替换”等操作实现方法，要求学生举例。给出一篇word文档 完成在上述文档中从当前位置向后查找“计算机”或者向前查找“计算机”字符串的方法。这些软件中“查找”操作是怎么实现的？提出问题教师给出如下任务：手动演示如下两个字符串的查找操作。例如：在串S=”abcabcabdabba”中查找T=” abcabd”的位置。学生分组讨论，演示“查找”过程，如图（教具演示）我们发现比较到S6 和T6不等时，怎么办？解决问题|简单匹配算法引入“简单匹配算法”给出上例的匹配过程前两步：第一趟、第二趟、学生完成匹配
2、后面过程第三趟、第四趟、要求学生计算匹配次数：通过4次匹配，终于在S串中“查找”到T串，位置时4在第一趟比较后，进行的第二趟、第三趟比较有必要吗？进一步提出问题第一趟后，当S6T6时，第二趟进行S2与T1比较是必要的吗？第三趟进行S3与T1比较是必要的吗？第四趟进行S4与T1比较是必要的吗？第四趟进行S4与T2比较是必要的吗？学生讨论，然后找学生提问，最后证明。如果是不必要的，那么第一趟后，当S6T6时，S6与T ？比较是必要的呢！“？”怎么求？KMP匹配算法引入“MP匹配算法”第一趟，当S6T6时，S下标不是回溯到2，T下标也不是回溯到开始，而是根据T中T6=d的模式函数值（next6=3，
3、为什么？后面讲）进行匹配，要求学生完成匹配过程当S6T6时，根据next6=3匹配过程：仅通过2次匹配，终于在S串中“查找”到T串，位置时4next6=3含义： 其实这个3表示T6=d的前面有2个字符和开始的两个字符相同”怎么求串的模式值 nextn？教学重点内容next值的计算引入“模式值nextn的计算”定义 ：略例二、求T=“abcab”的模式函数的值。下标12345Tabcnext设T=“abcab”，S“abcadcabcab”，利用KMP算法进行匹配，几次匹配成功？存在什么问题？问题的进一步提出第一趟：当出现S5T5时，根据next5=2,得：学生完成后面的工作：仅通过5次匹配，在
4、S串中“查找”到T串，位置时7比如：“abcab”模式串中，NEXT值为（0 1 1 1 2 ）。当比较到T5=b不成功时，原NEXT的值跟T2比较，可事实上，T2也是b，与T5相同，所以可以直接跟T1比较。可见，第二趟比较是多余的，那么如何改进呢？nextval值的计算nextn 改进为nextvaln：如果TjTk，k=nextj 否则k=nextk要求学生计算nextval值nextval?根据nextval，计算改进后的匹配次数。完成理论教学目标，那么在计算机中我们怎样编程实现？另外几种算法的时间复杂度怎样计算？成品介绍ADT演示：介绍抽象数据类型的简单匹配算法实现及其时间复杂度计算方
5、法。进一步认识“数据封装”的含义，在原有程序基础上增加“匹配次数”的计算方法:结果：怎样实现KMP算法及其改进的模式匹配算法主动式学习与模仿KMP算法实现教师辅导学生模仿“简单匹配算法”实现代码，实现“KMP算法”程序调试过程时，学生可以向下面的学生求助，也可以向老师求助进一步熟悉了ADT编程方法和调试机巧课堂作业1. 给出字符串abacabaaad在KMP算法中的next和nextval数组。2对S=aabcbabcaabcaaba，T=bca，画出T为模式串，S为目标串的匹配过程。10分钟完成，并检查掌握情况课后作业：1求串ababaaababaa 的next函数值。2模式串t=abcaa
6、bbcaabdab，求模式串的next和nextval函数的值。提高创新仿照WORD文档中的“查找”操作，编程实现在文本文件中查找指定的字符串位置。学生讨论，查找相关文献资料将结果上传至作业存储的ftp服务器ftp:/219.231.49.249网上答疑课堂作业、课后作业答案将在数据结构在线学习网站网站公告”中公布在学习过程中遇到的不懂的、或者难题，请同学继续在“数据结构在线学习网站网上答疑”中提交对于“网上答疑”中的问题，我们将及时回复，目前“网上答疑”的开通，极大的方便了老师与学生的交流，反映效果较好。附：详细的教学过程1、创设情境，引入课题老师：学生：完成在上述文档中从当前位置向后查找“
7、计算机”或者向前查找“计算机”字符串的方法。2、提出问题，解决问题手动演示如下两个字符串的查找操作，例如：学生分组讨论，演示“查找”过程，如图1（教具演示）老师提出问题：解决问题：3、 简单匹配算法 基本的模式匹配算法：以主串的某个字符与子串的第一个字符相比较，若相等，则继续比较二者的后一个字符，否则主串的字符指针从开始与子串第一个字符比较处后移一个位置，而子串的字符指针重新指向子串的第一个字符。当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。又一次发生了失配，所以T下标
8、又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标4。上述通过4次匹配，终于在S串中“查找”到T串，位置时4。老师再次提出问题：提问的形式：让学生讨论如下问题，第二趟进行S2与T1比较是必要的吗？第三趟进行S3与T1比较是必要的吗？第四趟进行S4与T1比较是必要的吗？第四趟进行S4与T2比较是必要的吗？ S6与T ？引入“KMP匹配算法”4、KMP 匹配算法 KMP算法：KMP算法是对传统模式匹配算法的较大改进，在传统的模式匹配算法中，当出现主串中的字符与子串中的字符不等时，同时向前回溯了两个指针，一个是主串的指针，一个是子串的指针。
9、而KMP算法的基本思路是在不回溯主串的指针，而只回溯子串的指针的情况下完成模式匹配，这样就省去了回溯主串指针进行比较的一部分时间。KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。还是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S6 和T6不等后，S下标不是回溯到2，T下标也不是回溯到开始，而是根据T中T6=d的模式函数值（next6=3，为什么？后面讲），直接比较S6 和T3是否相等，因为相等，S和T的下标同时增加;因为又相等，S和T的下标又同时增加。最终在S中找到了T。 其实这个3表示T6=d的前面有
10、2个字符和开始的两个字符相同”。请看图：因为，S5 =T5，S4 =T4，根据next6=3，有T4=T1，T5 =T2，所以S4=T1，S5 =T2（两对相当于间接比较过了），因此，接下来比较S6 和T3是否相等。有人可能会问：S4和T1，S5 和T2是根据next6=3间接比较相等，那S2和T1，S3 和T1之间又是怎么跳过，可以不比较呢？因为S1=T1，S2=T2，S3=T3，而T1!=T2, T2T3,=S1= S2,S2 != S3,所以S2= T1,S3 != T1.还是从理论上间接比较了。5 . 怎么求串的模式值 nextn 0 如果j=1nextj= Maxk|1kj且p1.p
11、k-1=pj-k+1.pj-1 1 其它情况（1）next1=0 意义：任何串的第一个字符的模式值规定为0。（2）nextj=k模式串T中下标为j的字符，如果j的前面k1个字符与开头的k1个字符相等， 即:T1T2Tk-1 = Tj-k+1Tj-k+2Tj-1（3）nextj=1 其他情况。例1）求T=“abcac”的模式函数的值。例2） 求T=”ababcaabc” 的模式函数的值。6789例3）求 T=”abCabCad” 的模式函数的值。Cd课后题：求 T=” ababcabababc” 的模式函数的值。6. nextn 不足与改进：KMP的改进算法：KMP的改进算法主要是针对求NEXT
12、数组的算法思想进行的改进。为了提高NEXT数组的效率，引入了NEXTVAL数组（即NEXT的改进值）。NEXTVAL避免了当出现匹配不成功时再接着进行重复比较的情况。“abcdabce”模式串中，NEXT值为（0 1 1 1 1 2 3 4），NEXTVAL值为（0 1 1 1 0 1 1 4）。当比较到T7=C不成功时，原NEXT的值跟T3比较，可事实上，T3也是C，与T7相同，所以可以直接跟T1比较。举例 ：若T=“abcab”的模式函数的值 若S“abcadcabcab”，如果Tj!=Tk，k=nextj 否则k=nextk练习：求T=”AAAAAAAAAAB” 的模式函数值，并用后面的
13、求模式函数值函数验证。7 . nextn 意义 ：设在字符串S中查找模式串T，若Sm!=Tn,那么，取Tn的模式函数值nextn,（1）、 nextn= 0 表示Sm和T1间接比较过了，不相等，下一次比较 Sm+1 和T1（2）、 nextn=1 表示比较过程中产生了不相等，下一次比较 Sm 和T1。（3）、 nextn=k 表示Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk相等吗？（4）、其他值，不可能。课后习题：1.求串ababaaababaa 的next函数值。2.模式串t=abcaabbcaabdab，求模式串的next和nextval函数的值。3.给出字符串abacabaaad在KMP算法中的next和nextval数组。4.S=aabcbabcaabcaaba，T=bca，画出以T为模式串，S为目标串的匹配过程。习题答案：1. 求串ababaaababaa 的next函数值。【解答】 j101112 串nextj1314nextvalj4对S=aabcbabcaabcaaba，T=bca，画出以T为模式串，S为目标串的匹配过程。 bca的next值数为: 011a a b c b a b c a a b c a a b ab c b b c a b c
