[理学]第09讲 串的模式匹配与串的应用.ppt

void Insert (LString S, int i, LString T ) { Chunk *P, *Q ; int j=0 ; P = S.head ; while ( P!=NULL ) ( ji-1 ) //查找第i-1位置 { j++; P = P-next; } Q = T.tail; //查找T串最后一个元素 if ( P!=NULL ) //插入 { Q-next=P-next; P-next=T.head-next; S.curlen += T.curlen; } else cout “error!” //找不到扦入位置 } 花费的时间主要在查找上，时间复杂度为O(n)。 第4章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.3.1 求子串位置的定位函数 4.3.2 模式匹配的一种改进算法 4.4 串操作应用举例 4.3 串的模式匹配算法 4.3.1 求子串位置的定位函数 又称模式匹配或串匹配，应用非常广泛。 在串匹配中，假设S为目标串，P为模式串： S=‘s1s2...sn’ P=‘p1p2…pm’ 串的匹配实际上是根据 1≤i≤n-m+1 依次将 S 的子串 S’[i…i+m-1] 和 P[1…m] 进行比较，若 S’[i…i+m-1] = P[1…m]，则称从位置i开始的匹配成功；反之，匹配失败。 上述的位置i又称为位移， 当S’[i…i+m-1] = P[1…m]时，i称有效位移； 当S’[i…i+m-1]≠ P[1…m]时，i称无效位移。 这样，串匹配问题可简化为是找出某给定模式串 P 在给定目标串 S 中首次出现的有效位移。 串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。 基本思想：用一个循环来依次检查 n-m+1个合法的位移i(1≤i≤n-m+1)是否为有效位移。 算法段： for(i=1;i=n-m+1;i++) if(S[i..i+m-1]=P[1..m]) return i; 例：模式匹配的算法 int Index(SString s,SString p,int pos){ j=1; i=pos; while (i= s[0] j= p[0] ) { if(s[i]= =p[j]){ i++; j++;} //继续比较后续字符 else { i=i-j+2; j=1; } //指针回溯到下一首位，重新开始匹配 } if(j p[0]) return i-p[0]; //匹配成功 else return 0; } // Index 相当于子串向右滑动一个字符位置 匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。 例： 设pos=1； 模式串T=‘abcac’ 算法简单并易于实现，但在某些情况下时间效率不高，主要的原因是主串下标i在若干个字符序列比较相等后只要有一个字符比较不相等时便需要把下标i的值回退。 算法的最坏情况是：当模式串p的前m-1个字符序列与主串s的相应字符序列比较总是相等，但模式串p的第m个字符与主串的相应字符比较总是不等时，模式串的m个字符序列必须与主串的相应字符序列块比较n-m+1次，每次比较m个字符，所以总共需比较m*(n-m+1)次，因此时间复杂度为O(n*m)。譬如：s=‘aaaaaaaa’,t=‘aab’ 4.3.2 模式匹配算法的改进算法(KMP算法) 1.匹配分析 KMP算法的特点主要是消除了上述算法的主串下标i在若干次字符序列比较相等后只要有一个字符比较不相等便把下标i的值回退的缺点。 分析上述算法可以发现，算法中的主串下标i值的回退并非一定必要。我们从2种情况来分析： 对于p中已与s前若干字符相匹配的部分p1～pj-1 第一种情况是： 模式串中不存在相等真子串的情况，即p1～pj-1中不存在前k（1kj-1）个字符等于后k个字符的情况。 例：主串s=‘cddcde’，模式串p=‘cde’的模式匹配过程。 当s1=p1，s2=p2，s3≠p3时，由于p1～pj-1=’cd’，k=2,情况１成立,即 p2≠p1，所以定有s2≠p1，接下来可直接比较 s3 和 p1。 第二种情况是： 模式串中存在相等真子串的情况，即p1～pj-1存在前k（1kj-1）个字符等于后k个字符的情况。 例：主串s=‘aaabaaad’，