厦门大学：《数据结构》课程教学课件（PPT讲稿）第四章 串（2/2）

4.3串的模式匹配算法 27

28 串的模式西配 子串的定位操作又称为模式匹配(Pattern Matching) 或串匹配(String Matching),其中子串T被称为模 式串。 此操作的应用在非常广泛。例如，在文本编辑程序 中，我们经常要查找某一特定单词在文本中出现的 位置。显然，解此问题的有效算法能极大地提高文 本编辑程序的响应性能

13 29 林素的模式巫配算法 第1趟S a bb a b a T a b a 穷举的模式匹配方法 【基本思想（同算法41）】 从主串S的第pos个字待 第2趟S a bb a b a 起和模式T的第一个字 T a 符比较，若相等，则继 续逐个比较后继字符， 第3趟S a bb 否则从主串的下一个字 ab a T 符起重新和模式T的字 符比较。依此类推，直 到找到匹配成功，或匹 第4趟S a bb a b 配失败。 T a b 返回i=4

30 林素的模式区配算法(3) it Index(SString S,SString T,int pos) ∥返回子串T在主串$中第3个字符之后的位量。若不存在，则函数值为0。 ∥其中，T非空，1≤pog≤StrLengt)(s)。 i=pas;j=1; h(i[0]) t i-[0]: alse ratura 0; k∥Index i-j+1 i-j+2 i-1 1 2

31 朴素的模式匹配算法(4) 算法简单，易于理解，但效率不高，主要原因是执 行中有回溯，一旦比较不等，就将指针右移一个字 符，并从模式串的开头重新开始比较。 ·在最坏的情况下，每趟比较都在最后出现不等，最多比 较n-m+1趟，总比较次数为m(n-m+1),由于在一般 情况下m<<n,所以算法运行时间为O(m*n)。 【例】 主串： 000000000000000000000000000000000000000000001 模式串： 00000001

32 改进的摸式区配算法—KMP算法 i=1i=2i3 D.E.Knuth与 第1趟S VR.Pratt和 a b.baba T a b J.H.Morris同时发现 a 的，故简称为MP算 法 第2趟S a bb a b a 指针不回湖！ T a =4i=5i6i= 第3趟S a bb ab T a b a 返回=4

33 改进的摸式西配算法—KMP(2) 第1趟S a b a b c a b c acba b T a b.c a c 每当出现失配时，指针不回 溯，而是利用已经得到的“部分 4 匹配”结果将模式向右“滑动”尽 可能远的一段距离后，继续比较 第2趟S a b ab c al b c a cb a b T j12j34 7i=8i9i=1010 第3趟S·a b a b c a b c,acba b T (a)b c a c 返回i=6 ◆◆ 臣23j456

34 失配时模式向右滑行的距离 假设主串sS2sa,模式串pP2Pm当主串 中第个字符与模式串中第j个字特失配”时，主串中 第i个字符应与模式串中第k个字符再比较 S-j+2 S1k+1 Sik+2 11 I| P2 P k+1 Pi-k+2 PH 滑动后 T P1 P2 卡4y Pk-1 【实质】k-1为pP2p1的最大相同真前缀真 后缀的长度！

35 模式串的next涵数定义 若令next[j们=k,则next[j们表明当模式串中第j个字符 与主串中第i个字符“失配”时，在模式串中需重新和 主串中该字符进行比较的字符的位置。 0,当j=时←此时，指针和应当同时增加1 Iext[]=Maxk1<k<J且'p卫，.P'=卫+1.P'子当此集合不空时 1,其它情况 next函数有时也称为失效函数。 。next函数值与i值无关！ 【例1】 【例2】 j 模式串 a a 模式串 ab a next[j] 0 nextj]

36 KMP算法 int Index.XMP(sString S,SString T,int pos) 利用馍式申T的next函数求T在主申s中第pog个字符之后的位量的 ∥nF算法。其中，T非空，1≤pos≤StrLength(s), 雨08；j=1: h1o(i[0])returD ] ∥匹配成功 意10x右0： l∥Index.ap 855生 int Index(SString S,SString T,int pos) ∥返回子串T在主串s中第9个字符之后的位量。若不存在，则函数值为0。 ∥其中，T非空，1≤po8≤StrLength(s)。 i-pos;j 1i (1r[oj）tm1-r[0]: ●lse5tugn0: B∥Index