《数据结构 第四章 串.ppt》由会员分享，可在线阅读，更多相关《数据结构 第四章 串.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第4 4章章 串串4.1 串的抽象数据类型定义串的抽象数据类型定义4.2 串的表示和实现串的表示和实现4.3 串的模式匹配算法串的模式匹配算法1理解串匹配的理解串匹配的KMP算法算法，熟悉，熟悉NEXT函数函数的定义，学会手工计算给定模式串的的定义，学会手工计算给定模式串的NEXT函数值和改进的函数值和改进的NEXT函数值。函数值。熟悉串的熟悉串的基本操作基本操作的定义，并能利用基本的定义，并能利用基本操作来实现串的其它各种操作的方法。掌操作来实现串的其它各种操作的方法。掌握握串的三种机内表示方法。串的三种机内表示方法。2p串串（string）：由由零零个个或或多多个个字字符符组组成成的的有
2、限序列。记为：有限序列。记为：s=a1a2a3an (n0)p串的长度串的长度：串中字符的数目：串中字符的数目n。p空串空串：零个字符的串，它的长度为零。：零个字符的串，它的长度为零。用用表示空串。表示空串。p空格串空格串：由一个或多个空格组成的串。：由一个或多个空格组成的串。3子串：子串：串中任意个串中任意个连续的字符连续的字符组成的子组成的子序列。序列。主串主串：包含子串的串。：包含子串的串。如：如：A=STUDYING ，B=DYI ，A为主串，为主串，B为子串。为子串。位置位置：字符在序列中的序号。：字符在序列中的序号。子串在主串中的位置子串在主串中的位置以子串的第一个字以子串的第一个
3、字符在主串中的位置来表示。符在主串中的位置来表示。串相等串相等的条件：当两个串的长度相等且的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。各个对应位置的字符都相等时才相等。4 串的抽象数据类型的定义如下串的抽象数据类型的定义如下：ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,ai D,i=2,.,n 串是有限长的字符序串是有限长的字符序列，由一对单引号相列，由一对单引号相括，如括，如:a string 5 基本操作基本操作：StrAssign(&T,chars)StrCopy(&T,S)
4、DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T,S1,S2)6SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)ADT String7 StrAssign(&T,chars)初始条件：chars 是字符串常量。操作结果：生成一个值等于 chars的串 T。8 StrCopy(&T,S)初始条件：串 S 存在。操作结果：由串 S 复制得串 T。9 D
5、estroyString(&S)初始条件：串 S 存在。操作结果：串 S 被销毁。10 StrEmpty(S)初始条件：串S存在。操作结果：若 S 为空串，则返回TRUE，否则返回 FALSE。表示空串，空串的长度为零。11StrCompare(S,T)初始条件：初始条件：串 S 和 T 存在。操作结果：操作结果：若S T，则返回值 0；若S T，则返回值 0；若S T，则返回值 0。例如：例如：StrCompare(data,state)012 StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。13 Concat(&T,S1,S2)初始条件：串 S1 和
6、S2 存在。操作结果：用 T 返回由 S1 和 S2 联接而成的新串。例如例如：Concate(T,man,kind)求得 T=mankind14 SubString(&Sub,S,pos,len)初始条件：串 S 存在，1posStrLength(S)且0lenStrLength(S)-pos+1。操作结果：用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。15例如：例如：SubString(sub,commander,4,3)求得 sub=man；SubString(sub,commander,1,9)求得 sub=commander；SubString(sub,co
7、mmander,9,1)求得 sub=r；子串为子串为“串串”中的一个字符子序列中的一个字符子序列16SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系起始位置和子串长度之间存在约束关系长度为长度为 0 的子串为的子串为“合法合法”串串17 Index(S,T,pos)初初始始条条件件：串S和T存在，T是非空串，1posStrLength(S)。操操作作结结果果：若主串 S 中存在和串 T 值相同 的子串,则返回它在主串 S 中第po
8、s个 字 符 之 后 第 一 次 出 现 的 位 置；否则函数值为0。18假设 S=abcaabcaaabc,T=bca Index(S,T,1)=2；Index(S,T,3)=6；Index(S,T,8)=0；“子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串中的位序位序。19 Replace(&S,T,V)初始条件：串S,T和 V 均已存在，且 T 是 非 空 串。操作结果：用V替换主串S中出现 的所有与（模式串）T 相等的不重叠的子串。20例如：假设 S=abcaabcaaabca，T=bca若 V=x，则经置换后得到 S=axaxaax若 V=bc，则经置换后得到 S
9、=abcabcaabc21 StrInsert(&S,pos,T)初始条件：串S和T存在，1posStrLength(S)1。操作结果：在串S的第pos个字符之前 插入串T。例如：例如：S=chater，T=rac，则执行 StrInsert(S,4,T)之后得到 S=character22 ClearString(&S)初 始 条 件：串 S存 在。操作结果：将S清为空串。23 StrDelete(&S,pos,len)初始条件：串S存在 1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符 起长度为len的子串。24 对于串的基本操作集可以有不同的定义对于串的
10、基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。型时，应以该语言的参考手册为准。gets(str)输入一个串；输入一个串；puts(str)输出一个串；输出一个串；strcat(str1,str2)串联接函数；串联接函数；strcmp(str1,str2)串比较函数；串比较函数；strlen(str)求串长函数求串长函数；例如例如：C语言函数库中提供下列串处理函数语言函数库中提供下列串处理函数25在上述抽象数据类型定义的13种操作中，串赋值串赋值StrAssign、串比较、串比较StrCompare 求串长求串长
11、StrLength、串联接串联接Concat 以及求子串以及求子串SubString 等五种操作构成串类型的最小操作子集等五种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子 集上实现。26 例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。StrCompare(SubString(S,i,StrLength(T),T)?0 S 串 T 串 T 串iposn-m+1算法的基本思想为：算法的基本思想为：27int Index(String
12、 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相等的子串/Index28 串的逻辑结构和线性表极为相似，区别区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。串的基本操作和线性
13、表有很大差别。在线性表的基本操作中，大多以大多以“单个单个元素元素”作为操作对象作为操作对象；在串的基本操作中，通常以通常以“串的整体串的整体”作为操作对象作为操作对象。29 在程序设计语言中，串只是作为输在程序设计语言中，串只是作为输入或输出的入或输出的常量常量出现，则只需存储此出现，则只需存储此串的串值，即字符序列即可。但在多串的串值，即字符序列即可。但在多数数非数值处理非数值处理的程序中，串也以的程序中，串也以变量变量的形式出现。的形式出现。30一、串的定长顺序存储表示一、串的定长顺序存储表示二、串的堆分配存储表示二、串的堆分配存储表示三、串的块链存储表示三、串的块链存储表示串有串有3
14、3种机内表示方法种机内表示方法31#define MAXSTRLEN 255 /用户可在255以内定义最大串长 typedef unsigned char SstringMAXSTRLEN+1;/0号单元存放串的长度一、串的定长顺序存储表示一、串的定长顺序存储表示32 按这种串的表示方法实现的串的运算时，其基本操作为“字符序列字符序列的复制的复制”。串串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断截断”。特点特点:33 Status Concat(SString S1,SString S2,SString&T)/用用T返回由返回由S1和和S2联接而成
15、的新串。若未截断联接而成的新串。若未截断,则返回则返回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
16、;T0.MAXSTRLEN=S10.MAXSTRLEN;/T0=S10=MAXSTRLEN uncut=FALSE;34按这种串的表示方法实现的串的运算时，按这种串的表示方法实现的串的运算时，其基本操作为其基本操作为“字符序列的复制字符序列的复制”。如果串值序列长度超过上界时，约定用如果串值序列长度超过上界时，约定用截尾法处理，克服这个弊病惟有不限定截尾法处理，克服这个弊病惟有不限定串长的最大长度，即串长的最大长度，即动态分配动态分配串值的存串值的存储空间。储空间。35 typedef struct char*ch;/若是非空串，则按串长分配存储区，/否则ch为NULL int length;
17、/串长度 HString;二、串的堆分配存储表示二、串的堆分配存储表示36 通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后 进行串值的复制。37Status Concat(HString&T,HString S1,HString S2)/用T返回由S1和S2联接而成的新串 if(T.ch)free(T.ch);/释放旧空间 if(!(T.ch=(c
18、har*)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;/Concat38 Status SubString(HString&Sub,HString S,int pos,int len)/用Sub返回串S的第pos个字符起长度为len的子串 if(pos S.length|len S.lengt
19、h-pos+1)return ERROR;if(Sub.ch)free(Sub.ch);/释放旧空间 if(!len)Sub.ch=NULL;Sub.length=0;/空子串 else /完整子串 return OK;/SubString 39 Sub.ch=(char*)malloc(len*sizeof(char);Sub.ch0.len-1=Spos-1.pos+len-2;Sub.length=len;40 和线性表的链式存储类似，也可用链表和线性表的链式存储类似，也可用链表方式来存储串值。方式来存储串值。由于串结构中的每个数据元素是一个字由于串结构中的每个数据元素是一个字符，则用链
20、表存储串值时，存在一个符，则用链表存储串值时，存在一个“结点大小结点大小”的问题，即每个结点可存放的问题，即每个结点可存放一个字符，也可以存放多个字符。当串一个字符，也可以存放多个字符。当串长不是结点大小的整数倍时，最后一个长不是结点大小的整数倍时，最后一个结点通常补上结点通常补上“#”或其他非串值字符。或其他非串值字符。三、串的块链存储表示三、串的块链存储表示4142为了便于进行串的操作，当以链表存储串为了便于进行串的操作，当以链表存储串值时，除值时，除头指针头指针外还可以附设一个外还可以附设一个尾指针尾指针指示链表中的最后一个结点，并给出当前指示链表中的最后一个结点，并给出当前串的长度串的
21、长度,称如此定义的串存储结构为称如此定义的串存储结构为块块链结构链结构。43#define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk /结点结构 char chCHUNKSIZE;struct Chunk *next;Chunk;typedef struct /串的链表结构 Chunk*head,*tail;/串的头和尾指针 int curlen;/串的当前长度 LString;44存储密度存储密度 =串值所占的存储位串值所占的存储位实际分配的存储位实际分配的存储位存储密度小（结点大小为存储密度小（结点大小为1时），运算处理时），运算处理方便，
22、然而，存储占用量大，如进行内、外方便，然而，存储占用量大，如进行内、外存交换的话，会因为交换操作过多而影响处存交换的话，会因为交换操作过多而影响处理的总效率。理的总效率。影响串值的存储方式选取的因素：影响串值的存储方式选取的因素：存储密度存储密度和和字符集的大小字符集的大小串的字符集大小也是一个重要因素。字符集串的字符集大小也是一个重要因素。字符集小，则字符的机内编码就短。小，则字符的机内编码就短。45例如例如:在编辑系统中，在编辑系统中，整个文本编辑区整个文本编辑区可可以看成是一个以看成是一个串串，每，每一行一行是一个是一个子串子串，构成一个结点。即构成一个结点。即:同一行的串用定长结同一行
23、的串用定长结构构,行和行之间用指针相联接。行和行之间用指针相联接。实际应用时，可以根据问题所需来设置实际应用时，可以根据问题所需来设置结点的大小。结点的大小。46 这是串的一种重要操作，很多这是串的一种重要操作，很多 软件，若有软件，若有“编辑编辑”菜单项的话，菜单项的话，则其中必有则其中必有“查找查找”子菜单项。子菜单项。47 若模式若模式T中的每个字符依次和主中的每个字符依次和主串串S中的一个连续的字符序列相等，中的一个连续的字符序列相等，则称则称匹配成功匹配成功，函数值为和模式，函数值为和模式T中第一个字符相等的字符在主串中第一个字符相等的字符在主串S中的序号。否则称中的序号。否则称匹配
24、不成功匹配不成功，函，函数值为零。数值为零。模式匹配：模式匹配：子串的定位操作子串的定位操作模式串：模式串：子串子串48初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos个字符之后第一次出 现的位置;否则函数值为0。首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)49模式匹配算法一：模式匹配算法一：Brute-ForceBrute-Force算法算法1 1、Brute-ForceBrute-Force算法的设计思想：算法的设计思想：将主串将主串S S的第一个字符和模式的第一个字符和模式T
25、T的第的第1 1个字符比较，个字符比较，若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符；若若不等不等，从主串，从主串S S的下一字符起，重新与的下一字符起，重新与T T第第一个字符比较。一个字符比较。直到主串直到主串S S的一个连续子串字符序列与模式的一个连续子串字符序列与模式T T相相等。返回值为等。返回值为S S中与中与T T匹配的子序列匹配的子序列第一个字符第一个字符的序号的序号，即匹配成功。，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0 0。2 2、Brute-ForceBrute-Force算法的实现算法的实现 50int Index(SString S,
26、SString T,int pos)/返回子串返回子串T在主串在主串S中第中第pos个字符之后的位置。若不存在，个字符之后的位置。若不存在，/则函数值为则函数值为0。其中，。其中，T非空，非空，1posStrLength(S)。i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/Index51ababcabcacbababcac第一趟匹配第一趟匹配第二趟匹配第二趟匹配ababcabcacbababcac第三趟匹配第三趟匹配ababcabcacbababcaci=3j=3i=2j=1i=7j=552第四趟匹配第四趟匹配ababcabcacba
27、babcac第五趟匹配第五趟匹配ababcabcacbababcac第六趟匹配第六趟匹配ababcabcacbababcaci=4j=1i=5j=1i=11j=653BF算法的时间复杂度讨论：讨论：若若n n为主串长度，为主串长度，m m为子串长度，则串的为子串长度，则串的BFBF匹配算法最坏的情况匹配算法最坏的情况下需要比较字符的总次数为下需要比较字符的总次数为(n-m+1)*mO(n*m)最好的情况是：最好的情况是：一配就中！一配就中！只比较了只比较了m m次。次。最恶劣情况是：最恶劣情况是：主串前面主串前面n-mn-m个位置都个位置都部分匹配部分匹配到子串的最后一到子串的最后一位，即这位
28、，即这n-mn-m位比较了位比较了m m次，别忘了最后次，别忘了最后m m位也各比较了一次，位也各比较了一次，还要加上还要加上m m！所以总次数为：所以总次数为：(n-m)*m+m(n-m+1)*m 能！能！而且主串而且主串S S的指针的指针i i不必回溯不必回溯！最坏情况也能！最坏情况也能达到达到O(n+m)O(n+m)请看请看KMP算法算法！当模式串为当模式串为00000001,主串为主串为00000000000000000000000000000000000000000000000000001时时,整个匹配过程中指针整个匹配过程中指针i需回溯需回溯45次次.能否利用已能否利用已部分匹配过
29、部分匹配过的信息的信息而加快模式串的滑动速度？而加快模式串的滑动速度？54模式匹配算法二：模式匹配算法二：KMP算法算法此改进算法是D.E.Knuth与V.R.Pratt和 J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特操作（简称KMP算法）55 a b a尽量利用已经尽量利用已经部分匹配部分匹配的结果信息；尽量让的结果信息；尽量让i i不要回溯，加快不要回溯，加快模式串的滑动速度。模式串的滑动速度。例：例：、KMPKMP算法设计思想：算法设计思想：S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c
30、b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a c需要讨论两个问题：需要讨论两个问题：如何由如何由当前部分匹配结果当前部分匹配结果确定模式向右滑动的新比较起点确定模式向右滑动的新比较起点k k？模式应该向右滑多远才是高效率的模式应该向右滑多远才是高效率的?i ii ii ik kk ka b ck ki ii i56S=a b a b c a b c a c b a bT=T=a b c a ci ik k请抓住部分匹配时的两个特征：请抓住部分匹配时的两个特征：两式联立可得：两式联立可得：“T T1 1TTk-1k-1”=T”=
31、Tj-k+1j-k+1 T Tj-1j-1 则则T T的的k-1k-1位位S S前前i-1i-1i-1i-1i-k+1)i-k+1)i-k+1)i-k+1)位位 设设目前打算与目前打算与T的第的第k字符开始比较字符开始比较(1)(1)(2)(2)T T1 1 T Tk-k-1 1 则则T T的的j-1j-1j-k+1j-k+1位位 S S前前i-1i-1i-1i-1i-k+1i-k+1i-k+1i-k+1)位位 刚才肯定是在刚才肯定是在S的的i处和处和T的第的第j字符字符 处失配处失配 T Tj-k+1j-k+1j-k+1j-k+1 T Tj-1j-1 截取一段，但截取一段，但截取一段，但截取
32、一段，但k k有限制，有限制，有限制，有限制，0kj0kjk k是追求的新起点是追求的新起点是追求的新起点是追求的新起点注意：注意：j 为当前已知的失配位置，我们的目标是计算新起点为当前已知的失配位置，我们的目标是计算新起点 k。式中仅剩一个未知数式中仅剩一个未知数k，理论上已可解！理论上已可解！T=T=a b c a cS=a b a b c a b c a c b a bi ik kj j奇妙的结果：奇妙的结果：奇妙的结果：奇妙的结果：k k 仅与模式串仅与模式串仅与模式串仅与模式串T T有关！有关！有关！有关！S Si-k+1 i-k+1 S Si-i-1 1 57结论：结论：设主串为设
33、主串为s1s2sn,模式串为模式串为p1p2pm,当当 Si Tj 时，主串中时，主串中第第i个字符与模式中第个字符与模式中第j个字符个字符“失配失配”时，时，仅需从模式中第仅需从模式中第k个字符和主串第个字符和主串第i个字符个字符比较起继续进行。比较起继续进行。5859定义：模式串的定义：模式串的next函数函数0 当当j=1时时Maxk|1kj 且且 p1pk-1=pj-k+1pj-1 当此集合不空时当此集合不空时1 其他情况其他情况Nextj=若令若令nextj=k,则则nextj表明模式中第表明模式中第j个字符比较个字符比较不等时，需将模式向右滑动至模式中第不等时，需将模式向右滑动至模
34、式中第k个字符和主个字符和主串中第串中第i个字符对齐。个字符对齐。注意：注意：注意：注意：（1 1）k k值仅取决于模式串本身而与相匹配的主串无关。值仅取决于模式串本身而与相匹配的主串无关。（2 2）k k值为模式串从头向后及从值为模式串从头向后及从j j向前的两部分的最大相同子串的向前的两部分的最大相同子串的长度。长度。（3 3）这里的两部分子串可以有部分重叠的字符，但不可以全部重）这里的两部分子串可以有部分重叠的字符，但不可以全部重叠。叠。取取P P首与首与PjPj处最大的相同子串处最大的相同子串60可见，模式中可见，模式中相似部分越多，则相似部分越多，则nextjnextj函数越大函数越
35、大，它既表示它既表示模式模式T字符之间的相关度越高，也表示字符之间的相关度越高，也表示j j位置位置以前与主串以前与主串部分匹配部分匹配的字符数越多。的字符数越多。即：即：nextjnextj越大，模式串向右滑动得越远越大，模式串向右滑动得越远，与主，与主串进行比较的次数越少，时间复杂度就越低（时间效串进行比较的次数越少，时间复杂度就越低（时间效率）。率）。61匹配过程：假设以指针i和指针j分别指示主串和模式串中正待比较的字符，令i的初值为pos，j的初值为1。若在匹配的过程中，si=pj,则,i,j分别加1；否则，j退回到某个next值得为止，以此类推。直到下列两种可能：j退回到某个next
36、值时字符相等，则指针分别加1，继续匹配。j=0（即模式的第一个字符失配），则从主串的下一个字符（i+1）起和模式重新匹配。62 int Index_KMP(SString S,SString T,int pos)/1posStrLength(S)i=pos;j=1;while(i=S0&j T0)return i-T0;/匹配成功 else return 0;/Index_KMP63问题：如何求 nextj?64求求next函数值的过程是一个递推过程，分析如下函数值的过程是一个递推过程，分析如下:已知：已知：next1=0；设设nextj=k,表明模式串中存在下列关系表明模式串中存在下列关系p
37、1.pk-1=pj-k+1pj-1,其中其中k为满足为满足1kj的的某某个值个值1.若若pkpj 则则nextj+1=k+1即即nextj+1=nextj+1(前前k个都相同个都相同)acbcdacbcg1k-1 j-k+1.j-1主串：acbcdacbcfnextj+1=k+1=5nextj 0 1 1 111 2 3 4 5652.若若pk pj 则表明则表明p1.pk pj-k+1pj 若若nextk=k 且且pj=pk,则存在则存在p1.pk pj-k+1pj 则则nextj+1=k+1即即nextj+1=nextk+1（前（前k个相同）个相同）acbddacbag主串：acbddac
38、baf1.k-1 j-k+1.j-1nextj+1=nextk+1=2因为k=1;nextj 0111 1 1 2 3 4 2663.若若pk pj 且且pj pk nextj+1=1（没有相同的）没有相同的）这实际上也是一个匹配的过程，不同在于：主串和模这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串式串是同一个串主串：acbcdacbdfacbcdacbdg1.k-1 j-k+1.j-1nextj+1=1nextj 0111 1 1 2 3 4 167 void get_next(SString&T,int&next)/求模式串T的next函数值并存入数组next i=1;ne
39、xt1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;/get_next68还有一种特殊情况需要考虑：还有一种特殊情况需要考虑：例如：例如：S=aaabaaabaaabaaabaaab T=aaaabnextvalj=00004nextj=0123469 void get_nextval(SString&T,int&nextval)i=1;nextval1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;if(Ti!=Tj)nextvali=j;else nextvali=nextvalj;else j
40、=nextvalj;/get_nextval70u=abcaabbabcabaacbacba1234567891011121314151617181920a b c a a b b a b c a b a a c b a c b anextjnextvalj0 1 1 1 2 2 3 1 2 3 4 5 3 22 1 1 2 1 1011 0 2 1 3 0 1 1 0 532 2 1 0 2 1 0例例：7112345678910A D A B B A D A D Anextj0 1 1 2 1 1 2 3 4 3nextvalj0 1 0 2 1 0 1 0 4 0s=ADBADABBAA
41、BADABBADADApat=ADABBADADA例例：722 2、KMPKMP算法的算法的时间复杂度时间复杂度注意：注意：由于由于BF算法在一般情况下的时间复杂度也近似于算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍被广泛采用。所以至今仍被广泛采用。而此时而此时KMPKMP的情况是：的情况是：由于指针由于指针i i无须回溯，比较次数仅为无须回溯，比较次数仅为n n,即使加上计算即使加上计算nextjnextj时所用的比较次数时所用的比较次数m m，比较总次数也仅比较总次数也仅为为n+m=n+m=O(nm)，大大快于大大快于BFBF算法。算法。回顾回顾BFBF的最恶劣情况：的最恶
42、劣情况：S S与与T T之间存在大量的之间存在大量的部分匹配，部分匹配，比较总比较总次数为：次数为：(n-m+1)*mO(n*m)因为主串指针因为主串指针i i i i不必回溯，所以从外存输入文件时可以做不必回溯，所以从外存输入文件时可以做到边读入边查找到边读入边查找“流水作业流水作业”！KMPKMP算法的用途：算法的用途：算法的用途：算法的用途：73 1.熟悉串的熟悉串的基本操作的定义基本操作的定义，并能利用，并能利用这些基本操作来实现串的其它各种操作这些基本操作来实现串的其它各种操作的方法。的方法。2.熟练掌握在串的熟练掌握在串的定长顺序存储结构定长顺序存储结构上上实现串的各种操作的方法。实现串的各种操作的方法。3.了解串的了解串的堆存储结构堆存储结构以及在其上实现以及在其上实现串操作的基本方法。串操作的基本方法。74 4.理解串匹配的理解串匹配的KMP算法，熟悉算法，熟悉NEXT函数的定义，学会手工计算给定模式串的函数的定义，学会手工计算给定模式串的NEXT函数值和改进的函数值和改进的NEXT函数值。函数值。5.了解串操作的应用方法和特点。了解串操作的应用方法和特点。75作业：作业：4.5,4.74.5,4.7，4.124.1276