(4.3.2)--4.3串的模式匹配-KMP算法1.ppt
《(4.3.2)--4.3串的模式匹配-KMP算法1.ppt》由会员分享,可在线阅读,更多相关《(4.3.2)--4.3串的模式匹配-KMP算法1.ppt(9页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1一、串的定义一、串的定义二、串的顺序表示二、串的顺序表示三、串的链式表示三、串的链式表示四、串的模式匹配四、串的模式匹配五、串的应用五、串的应用ontents2 模式匹配的改进算法模式匹配的改进算法KMP算法算法1 1、KMPKMP算法设计思想算法设计思想2、KMPKMP算法的推导过程算法的推导过程3 3、KMPKMP算法的实现算法的实现(关键技术(关键技术:计算计算nextjnextj)4 4、KMPKMP算法的时间复杂度算法的时间复杂度ontents31 1、KMPKMP算法设计思想算法设计思想S=a b a b c a b c a c b a bT=T=a b c a cS=a b a
2、 b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cIndex_kmpIndex_kmp的返回值应为的返回值应为i-5=6i-5=6需要讨论两个问题:需要讨论两个问题:如何如何“记忆记忆”部分匹配结果?部分匹配结果?如何由如何由“记忆记忆”结果计算出主串结果计算出主串S S第第i i个字符应该与模式个字符应该与模式T T中中哪个字符再比较?即确定模式哪个字符再比较?即确定模式T T中的新比较起点中的新比较起点k k.i ii ii ik kk k a b aa b c=1=3=7i i=11第第第第1
3、 1趟趟趟趟 S=S=a b a b a a b a a b c a c a a b c T=T=a b a a b c a c 第第第第2 2趟趟趟趟 S=S=a b a b a a b a a b c a c a a b c T=T=(a)b a a b c a c 第第第第3 3趟趟趟趟 S=S=a b a b a a b a a b c a c a a b c T=T=(a b)a a b c a c i=4i=4j=4i=8j=3j=9i=1i=14j=6j=2i=8串串S的指针的指针i不回溯!模式串不回溯!模式串T向右滑动,寻找合适的下一个向右滑动,寻找合适的下一个ji-T0或i-
4、j+1j=1 41 1、KMPKMP算法设计思想:算法设计思想:S=a b a b c a b c a c b a bT=a b c a cS=a b a b c a b c a c b a bT=a b c a cS=a b a b c a b c a c b a bT=a b c a cIndex_kmpIndex_kmp的返回值应为的返回值应为i-5=6i-5=6需要讨论两个问题:需要讨论两个问题:如何如何“记忆记忆”部分匹配结果?部分匹配结果?如何由如何由“记忆记忆”结果计算出主串结果计算出主串S S第第i i个字符应该与模式串个字符应该与模式串T T中哪个字符再比较?即确定模式串中哪
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 4.3 模式 匹配 KMP 算法
限制150内