数据结构串的模式匹配本.ppt
第四章 串的模式匹配算法本讲内容4.3 4.3 串的模式匹配算法串的模式匹配算法1.朴素的模式匹配算法朴素的模式匹配算法2.KMP算法算法1.模式串的模式串的nextnext和和nextvalnextval函数值函数值 2.2.手工模拟手工模拟KMPKMP算法的执行过程算法的执行过程 采用串的定长顺序存储结构，讨论不依赖于其他采用串的定长顺序存储结构，讨论不依赖于其他串操作的模式匹配算法（子串定位操作）。串操作的模式匹配算法（子串定位操作）。朴素的模式匹配算法Index(S,T,pos)算法思想算法思想从主串S的第pos个字符起和模式T的第一个字符比较，若相等，则继续逐个比较后续字符；否则，从主串的下一个字符起再重新和模式T的字符比较。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。匹配成功时，返回和模式T中第一个字符相等的字符在主串S中的位置；匹配失败时，返回零。朴素的模式匹配算法 S S 串串posi T 串jijijijij T 串朴素的模式匹配朴素的模式匹配 w 主串 S=ababcabcacbab，模式串T= abcac，pos=1 i=3第一趟匹配：第一趟匹配： a b a b c a b c a c b a b a b c j=3 i=2第二趟匹配：第二趟匹配： a b a b c a b c a c b a b a j=1 i=7 第三趟匹配：第三趟匹配： a b a b c a b c a c b a b a b c a c j=5 第四趟匹配：第四趟匹配： a b a b c a b c a c b a b a j=1 i=5 第五趟匹配：第五趟匹配： a b a b c a b c a c b a b a j=1 i=11 第六趟匹配：第六趟匹配： a b a b c a b c a c b a b a b c a c（成功）（成功） j=6 i=4int Index(SString S, SString T, int pos) / / 返回子串返回子串T T在主串在主串S S中第中第pospos个字符之后的位置。若不存在，个字符之后的位置。若不存在， / / 则函数值为则函数值为0 0。其中，。其中，T T非空，非空，1posStrLength(S)1posStrLength(S)。 i = pos; j = 1; while (i = S0 & j T0) return i - T0; else return 0; / Indexi- j +2;算法分析2.算法最坏情况下的时间复杂度为算法最坏情况下的时间复杂度为O(n*m)1.如果主串中可能存在多个和模式串如果主串中可能存在多个和模式串“部分部分匹配匹配”的子串，因而引起主串中指针的子串，因而引起主串中指针i的多的多次回溯。次回溯。上面的模式匹配只需三趟w 主串S=ababcabcacbab，模式串T= abcac i=3第一趟匹配第一趟匹配： a b a b c a b c a c b a b a b c j=3 (next3=1) i=3第二趟匹配第二趟匹配： a b a b c a b c a c b a b a b c a c j=5 (next5=2) i=7 第三趟匹配第三趟匹配： a b a b c a b c a c b a b (a)b c a c j=2 怎么得来的呢？这就是怎么得来的呢？这就是KMPKMP算法算法。KMP算法KMPKnuth, Morris, Pratt三人发明三人发明 特点：特点： p无需回溯； p在O(nm)的时间量级上完成串的模式匹配操作； KMP算法假设主串假设主串S S为为s1s2s3sn，模式串，模式串T为为p1p2pm，若，若si与与pj发发生失配，则有：生失配，则有： si-j+1si-1=p1pj-1 (1)(1) 由由（1），），若若kj,则有则有： si-k+1si-1= pj-k+1pj-1 (3)(3)若主串不回溯，设此时将与模式串中第若主串不回溯，设此时将与模式串中第k（kj）个字符继续比个字符继续比较，则有：较，则有： si-k+1si-1= p1pk-1 (2) (2) 由（由（2 2）和（）和（3 3），则下式成立：），则下式成立： p1pk-1 =pj-k+1pj-1 （4 4）该等式只与模式串有关，与主串无关。该等式只与模式串有关，与主串无关。KMP算法模式串的next函数定义定义其它情况当此集合不空时且时当1 . jk1 |kmax101111jkjkppppjjnext若模式串若模式串P为为 abaabc，由定义可得，由定义可得next函数值：函数值： j 1 2 3 4 5 6 模式串模式串 a b a a b cnextj 0 1 1 2 2 3 i=2第一趟匹配：第一趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a b j=2 next2=1 i=2第二趟匹配：第二趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a j=1 next1=0 i=3 i=8第三趟匹配：第三趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a b a a b c j=1 j=6 next6=3 i=8 i=12第四趟匹配：第四趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 (a b) a a b c j=3 j=7 KMPKMP算法算法手工模拟手工模拟主串主串 S= a c a b a a b a a b c a c a a b c模式串模式串 T= a b a a b c int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i = S0 & j T0) return i-T0; / 匹配成功 else return 0; / Index_KMP不存在这样的k，则nextj+1=1求求next函数值的过程是一个函数值的过程是一个递推递推过程，分析如下过程，分析如下: :已知：next1 = 0；假设：nextj = k；则：nextj+1 = k+1若：Tj Tk则需往前回溯，检查Tj = =T ？又又 Tj = =Tkk=nextj即：nextj+1 = nextj+1k即：nextj+1 = nextk+1j j12345678模式串模式串b ba ab bb ba ab ba ab b 0 1 1 2 2 3 4 3求模式串的next函数值举例这实际上也是一个匹配的过程，这实际上也是一个匹配的过程，不同在于：不同在于：主串和模式串是同一个串主串和模式串是同一个串 void get_next(SString &T, int &next ) / 求模式串T的next函数值并存入数组next j = 1; next1 = 0; k= 0; while (j T0) if (k = 0 | Tj = Tk)j=j+1; k=k+1; nextj = k; else k = nextk; / get_nextnext函数的改进改进当i4、j4时sipj，由nextj的指示还需进行i4、j3， i4、j2，i4、j1等三次比较。w实际上，由于模式中第第1、2、3个字符个字符和第第4个字符个字符都相等相等，因此这种比较是不必要不必要的，可以将模式串一次向右滑动一次向右滑动4 4个字符个字符直接进行i5、j1的比较。也就是说，若若nextj=k，当，当si与与pj失配失配且且pjpk，则下一步不需将主串中的，则下一步不需将主串中的si与与pk比较，而是直接与比较，而是直接与nextk进行比较。进行比较。 j j1 2 3 4 51 2 3 4 5 模式串a a a a ba a a a b nextjnextj0 1 2 3 40 1 2 3 4 nextvalj nextvalj 0 0 0 0 00 0 0 4 4主串主串a a a b a a a a ba a a a b void get_nextval(SString &T, int &nextval) j = 1; nextval1 = 0; k = 0; while (j T0) if (k = 0 | Tj = Tk) j=j+1; k=k+1; if (Tj != Tk) nextj = k; else nextvalj = nextvalk; else k = nextvalk; / get_nextval
