(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中哪个字符再比较？即确定模式串中哪

5、个字符再比较？即确定模式串T T中的新比较起点中的新比较起点j j。i ii ii ij=2j=2j=1j=1 a b aa b c=1=3=7i i=11j=3j=5j=5j=6j=65S S1 Si-j+1Si-j+2 Si-k+1-k+1 Si-2 Si-1 Si Si+1 Sn P p1 p2 pj-k+1-k+1 pj-2-2 pj-1 pj pm?p1 pk-2-2 pk-1 pk 则有则有则有则有 p1 p2 pj-1=Si-j+1 Si-2 Si-1 (1)假设假设下一个下一个j j为为k(kj)k(kj)，k k应该满足：应该满足：p1 p2 pk-1 =Si-k+1Si-k

6、+2 Si-1 (2)综合综合综合综合(1)(2)(1)(2)(1)(2)(1)(2)两式两式两式两式:p1 p2pk-1 =pj-k+1 pj-k+2 pj-1(3)2、KMP算法的推导过程算法的推导过程62、KMP算法的推导过程算法的推导过程已知当前失配位置已知当前失配位置j，可以归纳出计算新起点，可以归纳出计算新起点 k的表达式。的表达式。令令k=next j，则，则next j 0 当当j1时时max k|1kj 且且P1Pk-1=Pj-(k-1)j-(k-1)Pj-1 1 其他情况其他情况 当此集合不空时当此集合不空时讨论：讨论：next j 有何意义？有何意义？一旦失配，应从模式串

7、一旦失配，应从模式串T中第中第next j 个字符开始与个字符开始与S的失配点的失配点i 重新匹配重新匹配 next j 怎么求？怎么求？首部K-1个字符尾部K-1个字符73 3、KMPKMP算法的实现算法的实现int Index_KMP(SString S,SString T,int pos)i=pos;j=1;while(i=S0&jT0)return i-T0;/子串结束，说明匹配成功子串结束，说明匹配成功 else return 0;/Index_KMP首先把模式T所有可能的失配点j所对应的nextj计算出来；8怎样计算模式怎样计算模式P所有可能的失配点所有可能的失配点 j 所对应的所

8、对应的 nextj？例：可能失配位例：可能失配位 j：1 2 3 4 5 6 7 8 模模 式式 串串 P：a b a a b c a c 新匹配位新匹配位 nextj：next j 0 当当j1时时max k|1kj 且且P1 Pk-1=Pj-(k-1)j-(k-1)Pj-1 1 其他情况其他情况0 1 1 2 23 1 2讨论：讨论：j=1时时:next j=0；因为属于因为属于“j=1”j=2时时:next j=1；因为属于因为属于“其他情况其他情况”j=3时时:是否是否k=2，只需查看，只需查看P1=P2 2?但不相等，所以但不相等，所以nextj=1j=4时时:是否是否k=2，3，只

9、需查看，只需查看P1=P3 3 和和P1P2=P2 2 P3 3?发现只有发现只有P1=P3，所以，所以k=2，即，即nextj=2K-1个K-1个9怎样计算模式怎样计算模式P所有可能的失配点所有可能的失配点 j 所对应的所对应的 nextj？例：可能失配位例：可能失配位 j：1 2 3 4 5 6 7 8 模模 式式 串串 P：a b a a b c a c 新匹配位新匹配位 nextj：next j 0 当当j1时时max k|1kj 且且P1 Pk-1=Pj-(k-1)j-(k-1)Pj-1 1 其他情况其他情况0 1 1 2 2 3 1 2讨论：讨论：j=5时时,k=2,3,4k=2时，查看时，查看P1=P4 4 abaa k=2k=3时，查看时，查看P1P2=P3 3P4 4 abaa 保持保持k=2k=4时，查看时，查看P1P2P3=P2 2P3 3P4 abaa 保持保持k=2 K-1个K-1个