资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,黄刘生,中国科学技术大学计算机系,国家高性能计算中心（合肥）,1,数据结构1,Ch.4 串,字符串是一种特殊的线性表，它的每个结点仅由一个字符组成,早期，串只能出现在输入输出中，以直接量形式出现，不参与运算,2,Ch.4 串字符串是一种特殊的线性表，它的每个结点仅由一个字,4,.1 串定义及运算,基本概念,串：零个或多个字符组成的有限序列,记为s=“a,1,a,2,a,n,”(n0),s为,串名,，引号中为,串值,a,i,：字母，数字等字符,串长度：n，n=0为空串,空白串：“”和“”之差别,3,4.1 串定义及运算 基本概念3,4,.1 串定义及运算,子串：串中任意个连续字符组成的子序列称为该串的,子串,，包含子串的的串称为,主串,特别地：,空串是任意串的子串,任意串是其自身的子串,串常量：只能引用，不能改变，一般用直接量表示,有的语言允许对其命名，如C+；,const char path=“dir/bin/appl”,串变量：可读写，一般有名字,4,4.1 串定义及运算子串：串中任意个连续字符组成的子序列称,4,.1 串定义和运算,基本运算,求串长 复制 拼接 比较,子串定位,C中,比较,相等：长度相等，且各对应位置上字符亦 相等,大小：字典序“axy”,“ba”,5,4.1 串定义和运算基本运算5,4,.1 串定义及运算,子串定位,子串在主串中首次出现时，该子串首字符对应主串中的位置序号,A=“This is a string”B=“is”序号为3,3 6,其它复杂操作：,均可用基本操作构成,C中有丰富的函数,6,4.1 串定义及运算子串定位6,4,.2 串的存储结构,单个字符，故有特殊技巧,静态存储分配的顺序串,直接用定长字符向量来表示，上界预先给定,#define MaxStrSize 256 /用户定义,Typedef char SeqStringMaxStrSize;,SeqString S;/S是可容纳255个字符的顺序串,终结符：0是C的串终结符，放在串值尾部,串长属性：若不设终结符,typedef struct,char chMaxStrSize;/可容纳256字符,int length;,SeqString,7,4.2 串的存储结构单个字符，故有特殊技巧7,4,.2 串的存储结构,动态存储分配的顺序串,用C的malloc和free动态申请和释放向量空间，有两种形式：,typedef char*string;/C中串库相当于使用此类/似定义,typedef struct,char*ch;,/若串非空，则按串实际长度分配，否则为NULL,int length；,Hstring,8,4.2 串的存储结构动态存储分配的顺序串8,4,.2 串的存储结构,链串,块链存储,结点大小,大小为1：,大小为3：,存储密度d,d=数据大小/结点大小,Ex.4.25,9,4.2 串的存储结构链串9,4,.3 串的模式匹配算法（串定位运算）,朴素的定位算法（串匹配）,主串：目标串,（正文串Target，Text）,子串：模式（串）,（子串，Pattern）,设T=“t,0,t,1,t,n-1,”,P=“p,0,p,1,p,m-1,”（0mn）通常m,n,应用：文本编辑，基因匹配等,10,4.3 串的模式匹配算法（串定位运算）朴素的定位算法（串匹,4,.3 串的模式匹配算法,思想：,对合法的位置0in-m（,合法位移,），依次将目标串中的子串Ti.i+m-1和模式串P0.m-1进行比较,若T i.i+m-1=P0.m-1,(即：“t,i,t,i+1,t,i+m-1,”=“p,0,p,1,p,m-1,”),则称从位置i开始的,匹配成功,；,否则，存在某个0jm-1，使t,i+j,p,j,，则称从位置i开始的,匹配失败,11,4.3 串的模式匹配算法思想：11,4,.3 串的模式匹配算法,有效位移：,若,Ti.i+m-1,=,P0.m-1，则i称为有效,位移,无效位移：,若Ti.i+m-1,P0.m-1，则i称为无效,位移,总结：,朴素的串匹配算法是对合法位移检查其是否 为有效位移,有时需在T中找到所有有效位移,通常找首次出现的有效位移,12,4.3 串的模式匹配算法有效位移：若Ti.i+m-1,4,.3 串的模式匹配算法,int NaiveStrMatch(SeqString T,SeqString P)/顺序串上实现,int i,j,k;,int m=P.length,n=T.length;,for(i=0;i=n-m;i+)/i为合法位移，检查其是否为有效位移,j=0;k=i;/j指向模式，k指向目标,while(jm,最坏情况发生在：,目标串是 a,n-1,b,模式串是 a,m-1,b /最后一次成功,用链串表示时定位运算为习题,15,4.3 串的模式匹配算法时间：15,4,.3 串的模式匹配算法,KMP算法（不带回溯）,下标仍从1算,原因分析,P右移1位,T：,t,i-j+1,t,i,t,i-j+1,t,i-j+2,t,i,t,i+1,P：p,1,p,j,p,1,p,j-1,p,j,原因：,没有利用部分匹配的结果,若能将模式串右移一段距离，则速度更快,回溯,比较点,16,4.3 串的模式匹配算法KMP算法（不带回溯）回溯比较点,4,.3 模式匹配算法,T:a b b a b a,P:a b a,失败时有：,p,1,=t,1,，p,2,=t,2,，p,3,t,3,若将P右移1位，则p,1,？t,2,，因为,p,1,p,2，,p,2,=t,2,p,1,t,2,，故右移1位后仍失败,若将P右移2位，则p,1,？t,3,，因为,p,1,=p,3,，p,3,t,3,p,1,t,3,，故右移2位后仍失败,结论：,上图比较失败时应直接将P右移3位（即i=1，2，3均为无效位移），即直接比较p,1,和t,4,，比较点不回溯。,Note：,上述观察告诉我们，分析模式本身，就可知道潜在的有效位移,17,4.3 模式匹配算法T:a b b a b,4,.3 模式匹配算法,若使比较点不回溯（i不回溯），,则当t,i,p,j,（,Ti-j+1.i-1=P1.j-1，即P的前j-1个字符与相应T上字符相等：t,i-j+1,t,i-1,=p,1,p,j-1,）时，,P中哪个字符应与t,i,继续比较？,因为i不动时，必定是将模式右移一段距离，所以不妨设p,k,（kj）应与t,i,继续比较。,Knuth发现，k值仅依赖于P的前j个字符的构成，与目标T无关。,采用next1.m数组，用nextj=k表示当t,i,p,j,时，下一 个应与t,i,比较的是p,k,若P中任何字符均无需与t,i,比较，则将p,1,与t,i+1,比较，此时令nextj=0。P右移最大,18,4.3 模式匹配算法若使比较点不回溯（i不回溯），18,4,.3 模式匹配算法,算法：若已知next1m,则匹配算法如下,P的右移位数为：,j-nextj,t,i-j+1,t,i,t,i-j+1,t,i-k+1,t,i,p,1,p,j,p,1,p,k,p,j,j-k,右移j-k,？,右移i-k+1-(i-j+1)=j-k,19,4.3 模式匹配算法算法：若已知next1m,则匹,int KMPMatch(char T,char P)/T0和P0分别表示长度,n=T0;m=P0;/长度,i=j=1;/开始 t,1,p,1,while(i=n&j0),j=k;/比较t,i,和p,k,:t,i,p,k,else,j=1;i+;,/比较t,i+1,和p,1,:t,i+1,p,1,/endif，endwhile,if(jm)/匹配成功,return i-m;/注意成功时，i和j均多加了1,else,return 0;/匹配失败,20,int KMPMatch(char T,char,时间：,循环主要取决于i，只增不减，因为n,m，所以时间为O(n),4.3 模式匹配算法,21,4.3 模式匹配算法21,next数组的性质,整数数组：0nextjj，即0 k0，则比较t,i,和p,k,，此时有:,T i-k+1.i-1=P 1.k-1 /长度为k-1,T i-j+1.i-1 =P 1.j-1 /失败前部分匹配，长度为j-1,P j-k+1.j-1=P1.k-1 /“p,1,p,k-1,”=“p,j-k+1,p,j-1,”,当t,i,p,j,时，k的值应等于串P1j-1中前后缀相等的子串的长度加1,T：t,i-j+1,t,i-k+1,t,i-1,t,i,p,1,p,j-k+1,p,j-1,p,j,/前j-1个字符相等,P右移j-k位：p,1,p,k-1,p,k,/前k-1个字符相等,4.3 模式匹配算法,？,22,next数组的性质4.3 模式匹配算法？22,当满足性质2的k有多个（即前后缀相等的子串有多个）时，应取最大的k值。,原因：k最大，模式P右移j-k最少，不丢失任何匹配机会。,例:,j 1 2 3 4,T a a a a b b b b,P a a a b,在P1.3中，k=3最大，j-k=1位右移最少，k=2，k=1时失去匹配机会,即P1.3中，前后缀相等的,最大真子串,为P1.2=P2.3，长度+1=3=k,4.3 模式匹配算法,P右移1位，匹配成功,P右移2位、3位均失败,23,当满足性质2的k有多个（即前后缀相等的子串有多个）时，应取最,4.3 模式匹配算法,真子串不包括自身，但包括空串,真子串：”aa”,“a”,“”,长度：2 1 0,k ：3 2 1,24,4.3 模式匹配算法真子串不包括自身，但包括空串24,4.3 模式匹配算法,若P1j-1不存在首尾相同的字符串，或者说仅存在长度为零的相同前后缀（空串）子串，则k=1，即p,1,与t,i,继续比较,特别地，若j=1（即t,i,p,1,），则P中任何字符无法与t,i,继续比较，P右移1位，将p,1,和t,i+1,继续比较。按next定义，可取next1=0（对任何P成立）。,综上所述，当t,i,p,j,时,0 j=1,P1j-1中前后缀相等的,最大真子串的长度加1,(包括空串),即：,Maxk|1kj 且”p,1,p,k-1,”=“p,j-k+1,p,j-1,”/k=1时,为空串,例：,j 1 2 3 4 5 6 7 8,P a b a a b c a c,nextj 0 1 1 2 2 3 1 2,nextj=,25,4.3 模式匹配算法若P1j-1不存在首尾相同的,4.3 模式匹配算法,next数组生成（递推法）,设nexti=j已知，求nexti+1(i1),由性质4告知我们，对任何模式P，总有next1=0,成立，给出了递推基础,next1nexti已知，且已知nexti=j,P1i-1中有：,“p,1,p,j-1,”=“p,i-j+1,p,i-1,”/最大真子串长度为j-1,扩充一个字符p,i,后，比较p,j,p,i,若p,i,=p,j,，则P1j=Pi-j+1i,即P1i中前后缀的最大真子串长度为j，故,nexti+1=j+1 或者 nexti+1=nexti+1,26,4.3 模式匹配算法next数组生成（递推法）26,4.3 模式匹配算法,若p,i,p,j,，则将求next值的问题看成是模式匹配问题，即P既为主串又为模式串,将P右移，用nextj=k作下标，比较p,k,p,i,即：令jnextj，如此反复比较p,i,p,j,至p,i,=p,j,（情况）或者,j=0，令nexti+1=1为止 /没有一个字符与p,i,比较,例子自己分析,？,目标串：p,1,p,i-j+1,p,i-k+1,p,i-1,p,i,模式串：p,1,p,j-k+1,p,j-1,p,j,p,1,p,k-1,p,k,27,4.3 模式匹配算法若pipj，则将求next值的问,4.3 模式匹配算法,void GetNext(char p,int next),/求模式串P的next数组（递推法）i-主串指针,i=1;j=0;next1=0;,m=P0;/模式串长度,while(i0,if(Pi=Pj),next+i=+j;/nexti+1=j+1,else/p,i,p,j,j=nextj;,/可改进为书上一样的算法,28,4.3 模式匹配算法void GetNext(cha,4.3 模式匹配算法,时间：O(m),KMP算法的时间加上求next数组后为O(n+m),当nm时，它远远优于朴素匹配，尤其是模式串 中存在很多“部分匹配”时,但当nm时，朴素匹配可能更好,next数组的改进,next性质5：,若t,i,p,j,时，设nextj=k0，应比较t,i,p,k,若已知p,k,=p,j,，则必有t,i,p,k,，此时应使用nextk=k,(k0)为下标继续比较：t,i,p,k,29,4.3 模式匹配算法时间：O(m)29,4.3 模式匹配算法,即可用下述方式节省时间：,当p,j,=p,k,时，将nextj置为nextk,此过程可重复！,例：,j 1 2 3 4 5 j P nextj nextvalj,P a a a a b 1 a 0 0,nextj 0 1 2 3 4 2 a 1 0,改进 nextvalj 0 0 0 0 4 3 a 2 0,p,j,p,2,p,3,p,4,p,5,4 a 3 0,p,k,p,1,p,2,p,3,p,4,5 b 4 4,t,i,p,2,比较t,i,p,next2,p,2,=p,1,next2 next1,t,i,p,3,t,i,p,next3,p,3,=p,2,next3next2,30,4.3 模式匹配算法即可用下述方式节省时间：tip2,4.3 模式匹配算法,求nextval算法,与书上不一样的算法，请比较,void GetNextVal(char P,int nextval)/求nextval,i=1;j=0;,nextval1=0;m=P0;,while(i0&Pi!=Pj),j=nextvalj;/出循环时j=0或Pi=Pj,i+;j+;,if(Pi=Pj),nextvali=nextvalj;/性质5,else,nextvali=j;/nextvali+1=j+1,时间仍为O(m),31,4.3 模式匹配算法 求nextval算法31,4.3 模式匹配算法,附：习题：求串的逆的递推算法,void f(char A,int n)void f(char A,int i,int j),i0;j n-1;if(ij),while(ij)Ai Aj;,Ai+Aj-;f(A,+i,-,j);,/开始调用f(A,0,n-1),尾递归改为非递归（循环）无需引入栈,迭代循环的特点：,每次迭代循环结束后才能开始下一次迭代循环,递归控制结构在前一次循环尚未完成时就开始了新的循环，因此需引入栈来保存被中断的循环状态,但尾递归的控制结构则与循环迭代无区别,32,4.3 模式匹配算法附：习题：求串的逆的递推算法32,4.3 模式匹配算法,Ex.4.7，4.8,33,4.3 模式匹配算法Ex.4.7，4.833,
展开阅读全文