《KMP 字符串模式匹配算法》教学课例Word文档格式.docx
- 文档编号:839463
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:15
- 大小:248.59KB
《KMP 字符串模式匹配算法》教学课例Word文档格式.docx
《《KMP 字符串模式匹配算法》教学课例Word文档格式.docx》由会员分享,可在线阅读,更多相关《《KMP 字符串模式匹配算法》教学课例Word文档格式.docx(15页珍藏版)》请在冰点文库上搜索。
6个
五、互动式教学过程
教学内容
教师活动
学生活动
目标状态
创设情境引入课题
目前的众多软件中,“查找”、“替换”等操作实现方法,要求学生举例。
给出一篇word文档
完成在上述文档中从当前位置向后查找“计算机”或者向前查找“计算机”字符串的方法。
这些软件中“查找”操作是怎么实现的?
提出问题
教师给出如下任务:
手动演示如下两个字符串的查找操作。
例如:
在串S=”abcabcabdabba”中查找T=”abcabd”的位置。
学生分组讨论,演示“查找”过程,如图(教具演示)
我们发现比较到S[6]和T[6]不等时,怎么办?
解决问题
|
简单匹配算法
引入“简单匹配算法”
给出上例的匹配过程前两步:
第一趟、
第二趟、
学生完成匹配后面过程
第三趟、
第四趟、
要求学生计算匹配次数:
通过4次匹配,终于在S串中“查找”到T串,位置时4
在第一趟比较后,进行的第二趟、第三趟比较有必要吗?
进一步提出问题
第一趟后,当S[6]≠T[6]时,
◆第二趟进行S[2]与T[1]比较是必要的吗?
◆第三趟进行S[3]与T[1]比较是必要的吗?
◆第四趟进行S[4]与T[1]比较是必要的吗?
◆第四趟进行S[4]与T[2]比较是必要的吗?
学生讨论,然后找学生提问,最后证明。
如果是不必要的,那么第一趟后,当S[6]≠T[6]时,
S[6]与T[?
]比较是必要的呢!
“?
”怎么求?
KMP匹配算法
引入“MP匹配算法”
第一趟,当S[6]≠T[6]时,
S下标不是回溯到2,T下标也不是回溯到开始,而是根据T中T[6]==’d’的模式函数值(next[6]=3,为什么?
后面讲)进行匹配,要求学生完成匹配过程
当S[6]≠T[6]时,根据next[6]=3匹配过程:
仅通过2次匹配,终于在S串中“查找”到T串,位置时4
next[6]=3含义:
其实这个3表示T[6]==’d’的前面有2个字符和开始的两个字符相同”
怎么求串的模式值next[n]?
教学重点内容
next值的计算
引入“模式值next[n]的计算”
定义:
略
例二、求T=“abcab”的模式函数的值。
下标
1
2
3
4
5
T
a
b
c
next
设T=“abcab”,S=“abcadcabcab”,利用KMP算法进行匹配,几次匹配成功?
存在什么问题?
问题的进一步提出
第一趟:
当出现S[5]≠T[5]时,根据next[5]=2,得:
学生完成后面的工作:
仅通过5次匹配,在S串中“查找”到T串,位置时7
比如:
“abcab”模式串中,NEXT值为(01112)。
当比较到T[5]=b不成功时,原NEXT的值跟T[2]比较,可事实上,T[2]也是b,与T[5]相同,所以可以直接跟T[1]比较。
可见,第二趟比较是多余的,那么如何改进呢?
nextval值的计算
next[n]改进为nextval[n]:
如果T[j]≠T[k],k=next[j]否则k=next[k]
要求学生计算nextval值
nextval
?
根据nextval,计算改进后的匹配次数。
完成理论教学目标,那么在计算机中我们怎样编程实现?
另外几种算法的时间复杂度怎样计算?
成品介绍
ADT
演示:
介绍抽象数据类型的简单匹配算法实现及其时间复杂度计算方法。
进一步认识“数据封装”的含义,在原有程序基础上增加“匹配次数”的计算方法:
结果:
怎样实现KMP算法及其改进的模式匹配算法
主动式学习与模仿
KMP
算法实现
教师辅导
学生模仿“简单匹配算法”实现代码,实现“KMP算法”
程序调试过程时,学生可以向下面的学生求助,也可以向老师求助
进一步熟悉了ADT编程方法和调试机巧
课堂作业
1.给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。
2.对S=’aabcbabcaabcaaba’,T=’bca’,画出T为模式串,S为目标串的匹配过程。
10分钟完成,并检查掌握情况
课后作业:
1.求串’ababaaababaa’的next函数值。
2模式串t=’abcaabbcaabdab’,求模式串的next和nextval函数的值。
提高创新
仿照WORD文档中的“查找”操作,编程实现在文本文件中查找指定的字符串位置。
学生讨论,查找相关文献资料
将结果上传至作业存储的ftp服务器
ftp:
//219.231.49.249
网上答疑
课堂作业、课后作业答案将在数据结构在线学习网站—网站公告”中公布
在学习过程中遇到的不懂的、或者难题,请同学继续在“数据结构在线学习网站—网上答疑”中提交
对于“网上答疑”中的问题,我们将及时回复,目前“网上答疑”的开通,极大的方便了老师与学生的交流,反映效果较好。
附:
详细的教学过程
1、创设情境,引入课题
老师:
学生:
完成在上述文档中从当前位置向后查找“计算机”或者向前查找“计算机”字符串的方法。
2、提出问题,解决问题
手动演示如下两个字符串的查找操作,例如:
学生分组讨论,演示“查找”过程,如图1(教具演示)
老师提出问题:
解决问题:
3、简单匹配算法
基本的模式匹配算法:
以主串的某个字符与子串的第一个字符相比较,若相等,则继续比较二者的后一个字符,否则主串的字符指针从开始与子串第一个字符比较处后移一个位置,而子串的字符指针重新指向子串的第一个字符。
当这样一个失配发生时,T下标必须回溯到开始,S下标回溯的长度与T相同,然后S下标增1,然后再次比较。
如图:
这次立刻发生了失配,T下标又回溯到开始,S下标增1,然后再次比较。
又一次发生了失配,所以T下标又回溯到开始,S下标增1,然后再次比较。
这次T中的所有字符都和S中相应的字符匹配了。
函数返回T在S中的起始下标4。
上述通过4次匹配,终于在S串中“查找”到T串,位置时4。
老师再次提出问题:
提问的形式:
让学生讨论如下问题,
第二趟进行S[2]与T[1]比较是必要的吗?
第三趟进行S[3]与T[1]比较是必要的吗?
第四趟进行S[4]与T[1]比较是必要的吗?
第四趟进行S[4]与T[2]比较是必要的吗?
S[6]与T[?
引入“KMP匹配算法”
4、KMP匹配算法
KMP算法:
KMP算法是对传统模式匹配算法的较大改进,在传统的模式匹配算法中,当出现主串中的字符与子串中的字符不等时,同时向前回溯了两个指针,一个是主串的指针,一个是子串的指针。
而KMP算法的基本思路是在不回溯主串的指针,而只回溯子串的指针的情况下完成模式匹配,这样就省去了回溯主串指针进行比较的一部分时间。
KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。
还是相同的例子,在S=”abcabcabdabba”中查找T=”abcabd”,如果使用KMP匹配算法,当第一次搜索到S[6]和T[6]不等后,S下标不是回溯到2,T下标也不是回溯到开始,而是根据T中T[6]==’d’的模式函数值(next[6]=3,为什么?
后面讲),直接比较S[6]和T[3]是否相等,因为相等,S和T的下标同时增加;
因为又相等,S和T的下标又同时增加。
。
最终在S中找到了T。
其实这个3表示T[6]==’d’的前面有2个字符和开始的两个字符相同”。
请看图
:
因为,S[5]==T[5],S[4]==T[4],根据next[6]=3,有T[4]==T[1],T[5]==T[2],所以S[4]==T[1],S[5]==T[2](两对相当于间接比较过了),因此,接下来比较S[6]和T[3]是否相等。
有人可能会问:
S[4]和T[1],S[5]和T[2]是根据next[6]=3间接比较相等,那S[2]和T[1],S[3]和T[1]之间又是怎么跳过,可以不比较呢?
因为S[1]=T[1],S[2]=T[2],S[3]=T[3],而T[1]
!
=
T[2],T[2]
T[3],==>
S[1]
=S[2],S[2]!
=S[3],所以S[2]
=T[1],S[3]!
=T[1].
还是从理论上间接比较了。
5.怎么求串的模式值next[n]
0
如果j=1
next[j]={Max{k|1<
k<
j且'
p1...pk-1'
='
pj-k+1...pj-1'
1
其它情况
(1)next[1]=0
意义:
任何串的第一个字符的模式值规定为0。
(2)next[j]=k
模式串T中下标为j的字符,如果j的前面k-1个字符与开头的k-1个字符相等,
即:
T[1]T[2]……T[k-1]==T[j-k+1]T[j-k+2]…T[j-1]
(3)next[j]=1
其他情况。
例1)求T=“abcac”的模式函数的值。
例2)求T=”ababcaabc”的模式函数的值。
6
7
8
9
例3)
求T=”abCabCad”的模式函数的值。
C
d
课后题:
求T=”ababcabababc”的模式函数的值。
6.next[n]不足与改进:
KMP的改进算法:
KMP的改进算法主要是针对求NEXT数组的算法思想进行的改进。
为了提高NEXT数组的效率,引入了NEXTVAL数组(即NEXT的改进值)。
NEXTVAL避免了当出现匹配不成功时再接着进行重复比较的情况。
“abcdabce”模式串中,NEXT值为(01111234),NEXTVAL值为(01110114)。
当比较到T[7]=C不成功时,原NEXT的值跟T[3]比较,可事实上,T[3]也是C,与T[7]相同,所以可以直接跟T[1]比较。
举例:
若T=“abcab”的模式函数的值
若S=“abcadcabcab”,
如果T[j]!
=T[k],k=next[j]否则k=next[k]
练习:
求T=”AAAAAAAAAAB”的模式函数值,并用后面的求模式函数值函数验证。
7.next[n]意义:
设在字符串S中查找模式串T,若S[m]!
=T[n],那么,取T[n]的模式函数值next[n],
(1)、next[n]=0表示S[m]和T[1]间接比较过了,不相等,下一次比较S[m+1]和T[1]
(2)、
next[n]=1
表示比较过程中产生了不相等,下一次比较S[m]和T[1]。
(3)、
next[n]=
k
表示S[m]的前k个字符与T中的开始k个字符已经间接比较相等了,下一次比较S[m]和T[k]相等吗?
(4)、
其他值,不可能。
课后习题:
1.求串’ababaaababaa’的next函数值。
2.模式串t=’abcaabbcaabdab’,求模式串的next和nextval函数的值。
3.给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。
4.S=’aabcbabcaabcaaba’,T=’bca’,画出以T为模式串,S为目标串的匹配过程。
习题答案:
1.求串’ababaaababaa’的next函数值。
【解答】
j
10
11
12
串
next[j]
13
14
nextval[j]
4.对S=’aabcbabcaabcaaba’,T=’bca’,画出以T为模式串,S为目标串的匹配过程。
bca的next值数为:
011
aabcbabcaabcaaba
bc
b
bca
bc
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- KMP 字符串模式匹配算法 KMP 字符串模式匹配算法教学课例 KMP 字符串 模式 匹配 算法 教学