第4章串 4.3串的模式匹配《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 串的块链存储表示 4.3 串的模式匹配 4.3 模式匹配 子串的定位运算通常称为串的模式匹配，是串处理中最重要的运算之一。设串s=“a1a2…an”，串 T=“b1b2…bm”(m≤n)，子串定位是要在主串S中找出一个与子串T相同的子串。通常把主串S称为目标，把子串T称为模式，把从目标S中查找模式为T的子串的过程称为“模式匹配”。匹配有两种结果出现：若S中有模式为T的子串，就返回该子串在S中的位置，当S中有多个模式为T的子串，通常只要找出第一个子串即可，这种情况称为匹配成功，若S中无模式为T的子串，返回值为零，称为匹配失败。 模式匹配过程如图4-12所示。 假设S=“abababac”， T=“abac”。 ① BF算法设计思想： 将主串的第pos个字符和模式的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。 BF算法 （又称古典或经典的、朴素的、穷举的） KMP算法（特点：速度快） 算法种类 直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 . S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ pos=5 Int Index(SString S, SString T) { i=0; j=0;m=strlen(S);n=strlen(T); while ( i<m && j<n ) { if (S[i] = = T[j] ) {++i;++j;} //继续比较后续字符 else {i=i-j+1; j=0;} //指针回溯到 下一首位，重新开始匹配 } if(j>=n) return i-n+1; //子串结束，说明匹配成功 else return 0; }//Index ② BF算法的实现—即Index（）操作的实现 （见教材P68） S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ pos=5 相当于子串向右滑动一个字符位置 匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。 i j 顺序存储结构的实现程序： int S_index(SString t,SString p,int pos){ int n,m,i,j; m=strlen(t);n=strlen(p); for(i=pos-1;i<=m-n;i++){ for(j=0;j<n&&t[i+j]==p[j];j++); if(j==n) return(i+1); } return(0); } 代码与上一算法描述的区别？ 当剩下长度不足模式长度时，终止循环。 但时间效率依然为O(mn) 讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为 (n-m+1)*m＝O(n*m) BF匹配算法的最坏时间复杂度 最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还要加上m！ 改进的算法： KMP算法（特点：速度快） KPM算法 由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法） 传统的字符串比较过程中失败后，目标的指针需回溯到本次比较的下一个位置，而模式的指针需要回溯到开始位置 举例说明： 目标 S=“ababcababa” 模式 T=“ababa” 传统比较法： 比较的次数： Times=5+1+3+1+1+5=16 KMP算法的思想是发现出模式内在的关联，减少回溯： 极端的例子 目标 S=“abcdabcabababcde” 模式 T=“abcde” 可以想见，由于模式T所有字符都不相等，所以如果某次比较失败后，目标指针根本不需要回溯！ ？？？ 目标 S=“abcdabcabababcde” 模式 T=“abcde” 设目标的指针为i，模式的当前指针为j S=“abcdabcabababcde” T=“abcde” 上式中，当i,j都为5时，比较失败，其时i不回溯，j从1开始，进行如下比较： S=“abcdabcabababcde” T=“abcde” 上例是