数据结构课件第4章

第四章第四章串串1【课前思考】【课前思考】1.串就是线性表串就是线性表的结论是否正确？的结论是否正确？从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。2.串和线性表的主要差别是什么？串和线性表的主要差别是什么？希望你带着这个问题开始这一章的学习，并能在学完这一章的内容之后能得出正确的结论。2【学习目标】【学习目标】1.理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。2.理解串类型的各种存储表示方法。3.理解串匹配的各种算法。3【重点和难点】【重点和难点】相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点难点是理解实现串匹配的串匹配的KMP算法算法的思想，但它不属本章学习的基本要求，更不是重点学习内容。【知识点】【知识点】串的类型定义、串的存储表示、串匹配、KMP算法4【学习指南】【学习指南】虽然目前各常用的高级语言中都已经实现了串类型，但由于它是通过软件实现的，因此作为一个软件工作者还是应该了解串的实现方法。本章没有必须完成的算法设计题，如果有兴趣可以试试以下几个题:4.10，4.11，4.13，4.17，4.18，4.23，4.28,4.30。其中前6个是练习串的基本操作的应用，后2个是和KMP算法相关的练习。54.1 串类型的定义串类型的定义4.2 串的表示和实现串的表示和实现4.3 串的模式匹配算法串的模式匹配算法64.1串的类型定义串的类型定义一、一、基本概念基本概念 1串的定义串的定义串串(string)是是由由零零个个或或多多个个字字符符组组成成的的有有限限序序列列，记记作作s=a1a2an，其其中中s为为串串的的名名字字，用用成成对对的的单单引引号号括括起起来来的的字字符符序序列列为为串串的的值值，但但两两边边的的引引号号不不算算串串值值，不不包包含在串中。含在串中。ai(1in)可以是字母、数字或其它字符。可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。为串中字符的个数，称为串的长度。2空串空串不含任何字符的串称为空串，它的长度不含任何字符的串称为空串，它的长度n=0，记为，记为s=。3空格串空格串含含有有一一个个或或多多个个空空格格的的串串，称称为为空空格格串串，它它的的长长度度n为为空格的个数，一般用符号空格的个数，一般用符号“”表示空串。表示空串。串是有限长的字符序串是有限长的字符序列，由一对单引号相列，由一对单引号相括，如括，如:a string 74子串、主串子串、主串 通通常常将将字字符符在在串串中中的的序序号号称称为为该该字字符符在在串串中中的的位位置置。子子串串在在主主串串中中的的位位置置则则以以子子串串的的第第一一个个字字符符在在主主串串中中的的位置来表示。位置来表示。若若一一个个串串是是另另一一个个串串中中连连续续的的一一段段，则则这这个个串串称称为为另另一一个个串串的的子子串串，而而另另一一个个串串相相对对于于该该串串称称为为主主串串。例例如如,串串s1=“abcdefg”，s2=“fabcdefghxyz”，则则s1为为s2的的子子串串，s2相对于相对于s1为主串。为主串。另另外外，空空串串是是任任意意串串的的子子串串，任任意意串串是是自自身身的的子子串串。若若一一个个串串的的长长度度为为n，则则它它的的子子串串数数目目为为 +1，真真子子串串个数为个数为 (除串本身以外的子串都称为真子串除串本身以外的子串都称为真子串)。当且仅当两个串的值相等时当且仅当两个串的值相等时,称这两个串是相等的，即称这两个串是相等的，即只有当两个串的长度相等只有当两个串的长度相等,并且每个对应位置的字符都相并且每个对应位置的字符都相等时才相等。等时才相等。8二、串的抽象数据类型的定义如下：二、串的抽象数据类型的定义如下：ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,ai D,i=2,.,n 9 基本操作基本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T,S1,S2)10SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)ADT String11 StrAssign(&T,chars)初始条件：chars 是字符串常量。操作结果：把 chars 赋为 T 的值。12 StrCopy(&T,S)初始条件：串 S 存在。操作结果：由串 S 复制得串 T。13 DestroyString(&S)初始条件：串 S 存在。操作结果：串 S 被销毁。14 StrEmpty(S)初始条件：串S存在。操作结果：若 S 为空串，则返回TRUE，否则返回 FALSE。表示空串，空串的长度为零。15 StrCompare(S,T)初始条件：初始条件：串 S 和 T 存在。操作结果：操作结果：若S T，则返回值 0；若S T，则返回值 0；若S T，则返回值 0。例如：例如：StrCompare(data,state)016StrLength(S)初始条件：串 S 存在。操作结果：返回 S 的元素个数，称为串的长度。17Concat(&T,S1,S2)初始条件：串 S1 和 S2 存在。操作结果：用 T 返回由 S1 和 S2 联接而成的新串。例如例如：Concate(T,man,kind)求得 T=mankind18 SubString(&Sub,S,pos,len)初始条件：串 S 存在，1posStrLength(S)且0lenStrLength(S)-pos+1。操作结果：用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。19例如：例如：SubString(sub,commander,4,3)求得 sub=man；SubString(sub,commander,1,9)求得 sub=commander；SubString(sub,commander,9,1)求得 sub=r；子串为子串为“串串”中的一个字符子序列中的一个字符子序列20SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系起始位置和子串长度之间存在约束关系长度为长度为 0 的子串为的子串为“合法合法”串串21 Index(S,T,pos)初始初始条件：条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：操作结果：若主串 S 中存在和串 T 值相同 的子串,则返回它在主串 S 中第pos个字符之后第一次出现的位置；否则函数值为0。22假设 S=abcaabcaaabc,T=bca Index(S,T,1)=2；Index(S,T,2)=6；Index(S,T,8)=0；“子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串中的位序位序。23 Replace(&S,T,V)初始条件：串S,T和 V 均已存在，且 T 是非空串。操作结果：用V替换主串S中出现 的所有与（模式串）T 相等的不重叠的子串。24例如：假设 S=abcaabcaaabca，T=bca若 V=x，则经置换后得到 S=axaxaax若 V=bc，则经置换后得到 S=abcabcaabc25 StrInsert(&S,pos,T)初始条件：串S和T存在，1posStrLength(S)1。操作结果：在串S的第pos个字符之前 插入串T。例如：例如：S=chater，T=rac，则执行 StrInsert(S,4,T)之后得到 S=character26 StrDelete(&S,pos,len)初始条件：串S存在 1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符 起长度为len的子串。27ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。28 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：29在上述抽象数据类型定义的13种操作中，串赋值串赋值StrAssign、串复制、串复制Strcopy、串比较串比较StrCompare、求串长、求串长StrLength、串联接串联接Concat以及求子串以及求子串SubString 等六种操作构成串类型的最小操作子集等六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子 集上实现。30 例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。StrCompare(SubString(S,i,StrLength(T),T)?0 S 串 T 串 T 串iposn-m+1算法的基本思想为：算法的基本思想为：31int Index(String S,String T,int pos)/T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个 这样的子串在S中的位置，否则返回0 if(pos 0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;else return i;/while /if return 0;/S中不存在与T相等的子串/Index32又如串的置换函数：Replace(&S,T,V)S 串 T 串 V 串 V 串pospos subinews 串sub33 串的逻辑结构和线性表极为相似，区别区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以大多以“单个元单个元素素”作为操作对象作为操作对象；在串的基本操作中，通常以通常以“串的整体串的整体”作为操作对象作为操作对象。34 在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2 串的表示和实现串的表示和实现35一、串的定长顺序存储表示一、串的定长顺序存储表示二、串的堆分配存储表示二、串的堆分配存储表示三、串的块链存储表示三、串的块链存储表示36一、串的定长顺序存储表示一、串的定长顺序存储表示 与与前前面面所所讲讲的的线线性性表表的的顺顺序序存存储储结结构构类类似似,用用一一组组地地址址连连续续的的存存储储单单元元存存储储串串的的字字符符序序列列。常常常常将将定定长长顺顺序序串串设设计计成成一一种种结结构构类类型型,串串的的存存储储分分配是在编译时完成的。配是在编译时完成的。37#define MAXSTRLEN 255 /用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN+1;/0号单元存放串的长度38或：或：typedef struct /*串结构定串结构定义义*/char chMAXLEN;int len;SString;39 按这种串的表示方法实现的串的运算时，其基本操作为“字符序列字符序列的复制的复制”。串串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断截断”。特点特点:40 Status Concat(SString S1,SString S2,SString&T)/用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。return uncut;/Concat例如：例如：串的联接算法中需分三种情况处理：T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断 else if(S10 MAXSTRSIZE)/截断 else /截断(仅取S1)T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;T0.MAXSTRLEN=S10.MAXSTRLEN;/T0=S10=MAXSTRLEN uncut=FALSE;41(1)串插入函数。串插入函数。StrInsert(s,pos,t)/*在串在串s中序号为中序号为pos的字符之前插入串的字符之前插入串t*/SString*s,t;int pos;int i;if(poss-len)return(0);/*插入位置不合法插入位置不合法*/if(s-len+t.lenlen+t.len-1;i=t.len+pos;i-)s-chi=s-chi-t.len;for(i=0;ichi+pos=t.chi;s-len=s-len+t.len;定长顺序存储的操作实施：定长顺序存储的操作实施：【算法【算法 串插入函数】串插入函数】42else if(pos+t.lenMAXLEN,但串但串t的字符序列可以全部插入的字符序列可以全部插入*/for(i=MAXSTRLEN-1;it.len+pos-1;i-)s-chi=s-chi-t.len;for(i=0;ichi+pos=t.chi;s-len=MAXLEN;else /*串串t的部分字符序列要舍弃的部分字符序列要舍弃*/for(i=0;ichi+pos=t.chi;s-len=MAXSTRLEN;return(1);43(2)串删除函数。StrDelete(s,pos,len)/*在串s中删除从序号pos起len个字符*/SString*s;int pos,len;int i;if(pos(s-len-len)return(0);for(i=pos+len;ilen;i+)s-chi-len=s-chi;s-len=s-len-len;return(1);【算法【算法 串删除函数】串删除函数】44(3)串复制函数。串复制函数。StrCopy(s,t)/*将串将串t的值复制到串的值复制到串s中中*/SString*s,t;int i;for(i=0;ichi=t.chi;s-len=t.len;【算法【算法 串复制函数】串复制函数】45(4)判空函数。判空函数。StrEmpty(s)/*若串若串s为空为空(即串长为即串长为0),则返回则返回1,否则返回否则返回0*/SString s;if(s.len=0)return(1);else return(0);【算法【算法 判空函数】判空函数】46(5)串比较函数。串比较函数。StrCompare(s,t)/*若若串串s和和t相相等等,则则返返回回0；若若st，则则返返回回1；若若st，则则返返 回回-1*/SString s,t;int i;for(i=0;is.len&ilen=0;return(1);【算法【算法 清空函数】清空函数】49(8)连接函数。连接函数。Concat(s,t)/*将串将串t连接在串连接在串s的后面的后面*/SString*s,t;int i,flag;if(s-len+t.lenlen;ilen+t.len;i+)s-chi=t.chi-s-len;s-len+=t.len;flag=1;50else if(s-lenlen;ichi=t.chi-s-len;s-len=MAXSTRLEN;flag=0;else flag=0;/*串串s的长度等于的长度等于MAXLEN,串串t不被连接不被连接*/return(flag);【算法【算法 连接函数】连接函数】51(9)求子串函数。求子串函数。SubString(sub,s,pos,len)/*将串将串s中序号中序号pos起起len个字符复制到个字符复制到sub中中*/SString*sub,s;int pos,len;int i;if(poss.len|lens.len-pos)sub-len=0;return(0);else for(i=0;ichi=s.chi+pos;sub-len=len;return(1);【算法【算法 求子串函数】求子串函数】52(10)定位函数。定位函数。StrIndex(s,pos,t)/*求串求串t在串在串s中的位置中的位置*/SString s,t;int pos;int i,j;if(t.len=0)return(0);i=pos;j=0;while(is.len&j=t.len)return(i-t.len);else return(0);【算法【算法 定位函数】定位函数】53 typedef struct char*ch;/若是非空串，则按串长分配存储区，/否则ch为NULL int length;/串长度 HString;二、串的堆分配存储表示二、串的堆分配存储表示特点：仍用一组地址连续的存储单元存储串的字符序列，但其存储空间是在程序执行过程中动态分配而得。54 通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后 进行串值的复制。55Status Concat(HString&T,HString S1,HString S2)/用T返回由S1和S2联接而成的新串 if(T.ch)free(T.ch);/释放旧空间 if(!(T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char)exit(OVERFLOW);T.ch0.S1.length-1=S1.ch0.S1.length-1;T.length=S1.length+S2.length;T.chS1.length.T.length-1=S2.ch0.S2.length-1;return OK;/Concat56 Status SubString(HString&Sub,HString S,int pos,int len)/用Sub返回串S的第pos个字符起长度为len的子串 if(pos S.length|len S.length-pos+1)return ERROR;if(Sub.ch)free(Sub.ch);/释放旧空间 if(!len)Sub.ch=NULL;Sub.length=0;/空子串 else /完整子串 return OK;/SubString 57 Sub.ch=(char*)malloc(len*sizeof(char);Sub.ch0.len-1=Spos-1.pos+len-2;Sub.length=len;58三、串的块链存储表示三、串的块链存储表示也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。存储密度存储密度=数据元素所占存储位实际分配的存储位59#define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk /结点结构 char chCHUNKSIZE;struct Chunk *next;Chunk;typedef struct /串的链表结构 Chunk*head,*tail;/串的头和尾指针 int curlen;/串的当前长度 LString;60 例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。实际应用时，可以根据问题所需来设置结点的大小。61 这是串的一种重要操作，很多 软件，若有“编辑编辑”菜单项的话，则其中必有“查找查找”子菜单项。4.3串的模式匹配算法串的模式匹配算法 子串的定位操作通常称为串的模式匹模式匹配配，是各种串处理系统中最重要的操作之一。62初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos个字符之后第一次出 现的位置；否则函数值为0。首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)63 下面讨论以定长顺序结构表示串时的几种算法。一、简单算法一、简单算法二、首尾匹配算法首尾匹配算法三、三、KMP(KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法算法64一、简单算法一、简单算法Brute-Force算法算法 例如例如,设目标串设目标串s=“cddcdc”,模式串模式串t=“cdc”。s的长的长度为度为n(n=6),t的长度为的长度为m(m=3)。用指针。用指针i指示目标串指示目标串s的当前比较字符位置的当前比较字符位置,用指针用指针j指示模式串指示模式串t的当前比的当前比较字符位置。较字符位置。BF模式匹配过程如下所示。模式匹配过程如下所示。65 这个算法简单这个算法简单,易于理解易于理解,但效率不高但效率不高,主要原因是主要原因是:主串指针主串指针i在若干个字符序列比较相等后在若干个字符序列比较相等后,若有一个字若有一个字符比较不相等符比较不相等,仍需回溯仍需回溯(即即i=i-j+1)。该算法在最好情。该算法在最好情况下的时间复杂度为况下的时间复杂度为O(m),即主串的前即主串的前m个字符正好个字符正好等于模式串的等于模式串的m个字符。在最坏情况下的时间复杂度个字符。在最坏情况下的时间复杂度为为O(n*m)。66int index(SqString s,SqString t)int i=0,j=0,k;while(is.len&j=t.len)k=i-t.len;/*返回匹配的第一个字符的下标返回匹配的第一个字符的下标*/else k=-1;/*模式匹配不成功模式匹配不成功*/return k;67 先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到 第n-1个字符。二、首尾匹配算法首尾匹配算法68 int Index_FL(SString S,SString T,int pos)sLength=S0;tLength=T0;i=pos;patStartChar=T1;patEndChar=TtLength;while(i=sLength tLength+1)if(Si!=patStartChar)+i;/重新查找匹配起始点 else if(Si+tLength-1!=patEndChar)+i;/模式串的“尾字符”不匹配 else return 0;/检查中间字符的匹配情况检查中间字符的匹配情况69 k=1;j=2;while(j tLength&Si+k=Tj)+k;+j;if(j=tLength)return i;else +i;/重新开始下一次的匹配检测70三、模式匹配的改进算法三、模式匹配的改进算法（KMP算法）算法）此方法由克努特(D.E.Knuth)莫里斯(J.H.Morris)普拉特(V.R.Pratt)同时发现。1.基本思想：基本思想：每当一趟匹配过程中出现字符不等时，不每当一趟匹配过程中出现字符不等时，不需回溯需回溯i指针，而是利用已得到的部分匹配结果，将模式指针，而是利用已得到的部分匹配结果，将模式串向右滑动尽可能远的一段距离后继续进行比较。串向右滑动尽可能远的一段距离后继续进行比较。避免多余的、不必要的比较，从而提高算法性能。算法避免多余的、不必要的比较，从而提高算法性能。算法总在总在0(n+m)的时间数量级上完成匹配操作。的时间数量级上完成匹配操作。712.KMP算法匹配实例：算法匹配实例：72 (1)模式串模式串t中没有真子串中没有真子串 真真 子子 串串 是是 指指 模模 式式 串串 t存存 在在 某某 个个 k(0 k j),使使 得得“t0t1tk”=“tj-ktj-k+1tj”成立。成立。例例如如t=cdc就就是是这这样样的的模模式式串串。在在图图4.6中中的的第第一一次次回回溯溯,当当s0=t0,s1=t1,s2t2时时,算算法法中中取取i=1,j=0,使使主主串串指指针针回回溯溯一一个个位位置置,比比较较s1和和t0。因因t0t1,所所以以一一定定有有s1t0。另另外外,因因有有t0=t2,s0=t0,s2t2,则则一一定定可可推推出出s2t0,所所以以也也不不必必取取i=2,j=0去去比比较较s2和和t0。可可直直接接在在第第二二次次比比较较时时取取i=3,j=0,比比较较s3和和t0。这这样样,模模式式匹匹配配过过程程主主串串指指针针i就就可可不必回溯。不必回溯。73 (2)模式串中存在真子串模式串中存在真子串 例如例如t=“abab”,由于由于“t0t1”=“t2t3”(这里这里k=1,j=3),则则存在真子串。设存在真子串。设s=“abacabab”,t=“abab”,第一次匹配第一次匹配过程如下所示。过程如下所示。此时不必从此时不必从i=1(i=i-j+1=1),j=0重新开始第二次匹重新开始第二次匹配。因配。因t0t1,s1=t1,必有必有s1t0,又因又因t0=t2,s2=t2,所以必有所以必有s2=t0。因此。因此,第二次匹配可直接从第二次匹配可直接从i=3,j=1开始。开始。74 现在我们讨论一般情况。现在我们讨论一般情况。设设s=s0s1sn-1,t=t0t1tm-1,当当sitj (0in-m,0jm)时时,存在存在:t0t1tj-1=si-jsi-j+1si-1 (4.1)若模式串中存在的真子串满足若模式串中存在的真子串满足:t0t1tk=tj-ktj-k+1tj(0kj)(4.2)由由(4.1)式式说说明明模模式式串串中中的的子子串串t0t1tk-1已已和和主主串串si-ksi-k+1si-1匹匹配配,下下一一次次可可直直接接比比较较si和和tk,若若不不存存在在(4.2)式式,则则结结合合(4.1)式式说说明明在在t0t1tj-1中中不不存存在在任任何何以以t0为为首首字字符符子子串串与与si-j+1si-j+2si-1中中以以si-1为为末末字字符符的的匹匹配配子子串串,下下一次可直接比较一次可直接比较si和和t0。75 为此为此,定义定义nextj函数如下函数如下:maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1”当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=t=“abab”t=“abab”对应的对应的nextnext数组如下数组如下:76由模式串由模式串t求出求出next值的算法如下值的算法如下:void GetNext(SqString t,int next)int j,k;j=0;k=-1;next0=-1;while(jt.len-1)if(k=-1|t.chj=t.chk)/*k为为-1或比较的字符相等时或比较的字符相等时*/j+;k+;nextj=k;else k=nextk;77int KMPIndex(SqString s,SqString t)/*KMP算法算法*/int nextMaxSize,i=0,j=0,v;GetNext(t,next);while(is.len&j=t.len)v=i-t.len;/*返回匹配模式串的首字符下标返回匹配模式串的首字符下标*/else v=-1;/*返回不匹配标志返回不匹配标志*/return v;78 设设主主串串s的的长长度度为为n,子子串串t长长度度为为m,在在KMP算算法法中中求求next数数组组的的时时间间复复杂杂度度为为O(m),在在后后面面的的匹匹配配中中因因主主串串s的的下下标标不不减减即即不不回回溯溯,比比较较次次数数可可记记为为n,所所以以KMP算法总的时间复杂度为算法总的时间复杂度为O(n+m)。例如例如,设目标串设目标串s=“aaabaaaab”,模式串模式串t=“aaaab”。s的长度为的长度为n(n=9),t的长度为的长度为m(m=5)。用指针。用指针i指示目指示目标串标串s的当前比较字符位置的当前比较字符位置,用指针用指针j指示模式串指示模式串t的当的当前比较字符位置。前比较字符位置。KMP模式匹配过程如下所示。模式匹配过程如下所示。7980 上述定义的上述定义的next在某些情况下尚有缺陷。例如在某些情况下尚有缺陷。例如,模式模式“aaaab”在和主串在和主串“aaabaaaab”匹配时匹配时,当当i=3,j=3时时,s.ch3t.ch3,由由nextj的指示还需进行的指示还需进行i=3、j=2,i=3、j=1,i=3、j=0等三次比较。实际上等三次比较。实际上,因为模式因为模式中的第中的第1、2、3个字符和第个字符和第4个字符都相等个字符都相等,因此因此,不需不需要再和主串中第要再和主串中第4个字符相比较个字符相比较,而可以将模式一次向而可以将模式一次向右滑动右滑动4个字符的位置直接进行个字符的位置直接进行i=4,j=0时的字符比较。时的字符比较。KMP算法的改进：算法的改进：81 这就是说这就是说,若按上述定义得到若按上述定义得到nextj=k,而模式而模式中中pj=pk,则为主串中字符则为主串中字符si和和pj比较不等时比较不等时,不需要不需要再和再和pk进行比较进行比较,而直接和而直接和pnextk进行比较进行比较,换句话换句话说说,此时的此时的nextj应和应和nextk相同。为此将相同。为此将nextj修正为修正为nextvalj。82由模式串由模式串t求出求出nextval值值:void GetNextval(SqString t,int nextval)int j=0,k=-1;nextval0=-1;while(jnext，再设一个对，再设一个对尾指针尾指针q-rear指向链队列尾部。指向链队列尾部。队列的链式存储结构可定义如下：队列的链式存储结构可定义如下：typedef struct node typedef struct char data;slnode*h;struct node*next;slnode;slnode *rear;lqtype;四、思考题四、思考题 1、比较链队列与链栈的相同点与不同点。比较链队列与链栈的相同点与不同点。2、在链队列中，、在链队列中，q-rear指针能否省指针能否省去？若能，怎样才能找到队尾？若能，怎样才能找到队尾？88实验六实验六 串的模式匹配串的模式匹配 一、实验目的一、实验目的 熟悉串的有关概念，掌握串的存储结构及串的模式匹配算法。二、实验内容二、实验内容 由用户随意输入两个串：主串S和模式串T，设S=s1s2sn，T=t1t2tm，且0m=n。用简单和KMP模式匹配算法判断模式串T是否在主串S中，若在，则输出模式串在主串的第一匹配位置，否则，匹配失败，返回零值。三、实验要点及说明三、实验要点及说明 简单模式匹配算法和KMP模式匹配算法的主要区别在于后者将有效利用已有的匹配结果，省去不必要的匹配过程，提高匹配性能。利用串的顺序存储结构实现实验内容。四、思考题四、思考题 能否用串的块链存储结构实现KMP算法？89重庆工商大学重庆工商大学计算计算机与信息工程学院机与信息工程学院90