数据结构第09讲_串的模式匹配与串的应用_C.ppt

1、第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=p1p2pm 串的匹配实际上是根据 1in-m+1 依次将 S 的子串 Si.i+m-1 和 P1.m 进行比较，若 Si.i+m-1 = P1.m，则称从位置i开始的匹配成功；反之，匹配失败。,上述的位置i又称为位移， 当Si.i+m-1 = P1.m时，

2、i称有效位移； 当Si.i+m-1 P1.m时，i称无效位移。 这样，串匹配问题可简化为是找出某给定模式串 P 在给定目标串 S 中首次出现的有效位移。,串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。 基本思想：用一个循环来依次检查 n-m+1个合法的位移i(1in-m+1)是否为有效位移。,算法段： for(i=1;i=n-m+1;i+) if(Si.i+m-1=P1.m) return i;,例： 设pos=1； 模式串T=abcac,例：模式匹配的算法 int Index(SString s,SString p,int pos) j=1; i=pos; while (

3、i p0) return i-p0; /匹配成功 else return 0; / Index,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,算法简单并易于实现，但在某些情况下时间效率不高，主要的原因是主串下标i在若干个字符序列比较相等后只要有一个字符比较不相等时便需要把下标i的值回退。 算法的最坏情况是：当模式串p的前m-1个字符序列与主串s的相应字符序列比较总是相等，但模式串p的第m个字符与主串的相应字符比较总是不等。 每次比较m个字符，比较n-m+1次，共比较m*(n-m+1)次，时间复杂度为O(n*m)。,4.3.2 模式匹配算法的改进算

4、法(KMP算法) 1.匹配分析 KMP算法的特点主要是消除了上述算法的主串下标i在若干次字符序列比较相等后只要有一个字符比较不相等便把下标i的值回退的缺点。 分析上述算法可以发现，算法中的主串下标i值的回退并非一定必要。我们从2种情况来分析：,对于p中已与s前若干字符相匹配的部分p1pj-1 第一种情况是： 模式串中不存在相等真子串的情况，即p1pj-1中不存在前k（1kj-1）个字符等于后k个字符的情况。 例：主串s=cddcde，模式串p=cde的模式匹配过程。 当s1=p1，s2=p2，s3p3时，由于p1pj-1=cd，k=2,情况成立,即 p2p1，所以定有s2p1，接下来可直接比较

5、 s3 和 p1。,第二种情况是： 模式串中存在相等真子串的情况，即p1pj-1存在前k（1kj-1）个字符等于后k个字符的情况。 例：主串s=aaabaaad，模式串p=aaad的模式匹配过程。 当 s1=p1，s2=p2，s3=p3，s4p4 时，有 p1=p3，还有 p1p2=p2p3，取最大的相等子串 p1p2=p2p3，有k=3，由于s2s3=p2p3,此时必然有 s2s3=p1p2,显然，接下来可直接比较 s4 和 p3。,总结以上2种情况可以发现： 一旦有比较不相等时，主串 s 的下标不必回退，主串的 si 可直接和模式串的 pk(1 kj-1）比较，k 的确定与主串 s 并无关

6、系，k 的确定只与模式串 p 本身的构成有关，即从模式串本身就可求出 k 的值。,利用已经部分匹配的结果而加快模式串的滑动速度，而且主串S的指针i不必回溯！可提速到O(n+m)！例：,S=a b a b c a b c a c b a b,P=a b c a c,S=a b a b c a b c a c b a b,P=a b c a c,S=a b a b c a b c a c b a b,P=a b c a c,Index_kmp的返回值应为i=6,需要讨论两个问题： 如何“记忆”部分匹配结果？ 如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比

7、较起点k。,a b a,a b c,KMP算法设计思想,抓住部分匹配结果的两个特征：,两式联立可得：P1Pk-1=Pj-(k-1) Pj-1 注意：j 为当前已知的失配位置，我们的目标是计算新起点 k，仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！,则S前i-1i-(k-1)位P的j-1j-(k-1)位 即(4-3）式含义,则P的k-11位S前i-1i-(k-1)位 即(4-2）式含义,刚才肯定是在S的i处和T的第j字符处失配,设目前应与T的第k字符开始比较,从模式串本身求出k的值 当主串的si和模式串的pj比较不等时，由于满足关系式 p1p2 pk-1 = pj-k+1pj-k+2

8、pj-1 则要确定与主串si比较的子串pk的k值，只需求出模式串p中的每个字符的nextj函数即可。,2.next函数 令 nextj=k ,则表示主串和子串第 j 个元素失配时，应与第 pk 个字符比较。 0 当j=1时 nextj= Max k|1kj，且p1 pk-1=pj-k+1 pj-1 当此集合不空时 1 其他情况,例：求下列模式串的nextj函数 模 式 串 T： a b a a b c a c 可能失配位 j ： 1 2 3 4 5 6 7 8 新匹配位 nextj :,0,1,1,2,2,3,1,2,讨论：,j=1时, next j = 0；因为属于“j=1”; j=2时,

9、next j = 1；因为属于“其他情况”；,刚才已归纳：,j=3时, 只需查看是否T1=T2；,j=4时, 要查看是否T1=T3 和T1T2=T2T3,j=5时, 要查看是否T1=T4、T1T2=T3T4和T1T2T3=T2T3T4,以此类推，可得后续nextj值。,例：求下列模式串的nextj函数 模式串 c d d c d e c e c d e a 下标j 1 2 3 4 5 6 7 8 9 10 11 12 nextj,0 1 1 1 2 3 1 2 1 2 3 1,例：模式匹配的KMP算法： int index(SString s,SString p,int pos) i=pos;

10、 j=1; while (i p0) return i-p0; else return 0; ,j=1时,next(j)=0,第4章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例,4.4.1 文本编辑,文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍的编辑排版等。常用的文本编辑程序有Word,Notepad,WPS,TC等，文本编辑的实质是修改字符数据的形式和格式，虽然各个文本编辑程序的功能不同，但基本操作是一样的，都包括串的查找、插入和删除等。,为了编辑方便，可以用分页符和换行符将文本分为若干页，每页有若干行。我们把文本当作一个字

11、符串，称为文本串，页是文本串的子串，行是页的子串。 我们采用堆存储结构来存储文本，同时设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符，同时建立页表和行表存储每一页、每一行的起始位置和长度。,假设有如下源程序： FUNC max(x，y：integer)：integer; VAR z：integer; BEGIN IF xy THEN z:=x; ELSE z:=y; RETURN(z); END;,该程序输入内存后放到一个堆中，如下图所示。其中为换行符。,页表,行表,本章小结,1.理解串的逻辑结构定义、物理存储结构表示； 2.掌握串的基本操作算法，注意不同存储结构下，串的操作算法

12、也有所不同；能熟练地上机编程，并能熟练进行串的基本运算； 3.理解并掌握串的模式匹配算法，特别是KMP算法；能够计算模式串的next 函数。,练1：串是由 字符组成的序列，一般记为 。,练2：现有以下4个字符串： a =BEI，b =JING，c = BEIJING ，d = BEI JING，问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？,a = 3，b = 4，c = 7，d = 8,a是a、c和d的子串，在a、c和d中的位置都是1,0个或多个,S=a1a2an,练4：令模式串 s=a a a b t=a b c a b a a u=a b c a a b b a b c

13、 a b a a c b a c b a 分别求出他们的next函数值。,练3：空串和空格串有无区别？ 答：有。空串(Null String)是指长度为零的串；而空格串(Blank String)，是指包含一个或多个空白字符 (空格键)的字符串。,练5：从串S中删除所有和串T相同的子串。 此题的操作等同于“以空串置换串S中所有和串T相同的子串。”,显然，算法的目标是构造如上所画的一个新串。,String Delete (String / Delete,练6：顺序串上的插入insert(&S,i,T) 要将T插入到S中第i个位置，则S串中第i个位置开始，一直到最后的字符，每个都要向后移动若干位，移动的位数为T串长度。具体实现如图。,void Insert(SStr