《第4章串》习题解答

1、第4章 串存储与基本操作的实现第四章 串存储与基本操作的实现本章学习要点熟悉串的相关概念以及串与线性表的关系重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题“串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。4.1串的基本概念4.1.1串的概念1串的定义串(string) 是由n个字符组成的有限序列

2、，记为：S=”a0a1a2an-1” (n0)。其中，S是串的名字，字符序列a0a1a2an-1是串的值，ai(0in-1)可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（null string）。从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。例如：（1）A=“X123” (长度为4的串)（2）B=“12345654321” (长度为11的串)（3）C=“Bei Jing” (长度为8的串)（4）D=“” (长度为0的空串)（5）E=“This

3、 is a string” (长度为16的串)（6）F=“ is a ” (长度为6的串)2子串、主串和位置串中任意连续的字符组成的子序列称为该串的子串；相应地，包含子串的串称为主串。串中的字符在串序列中的序号称为该字符在该串中的位置；子串的第一个字符在主串中的位置称为子串在主串中的位置。显然，串为其自身的子串，并规定空串为任何串的子串。显然，在不考虑空子串的情况下，一个长度为n的字符串具有n(n+1)/2个子串。例如：在上例的(6)中串F就是(5)中串E的子串，且子串F在主串E中的位置是5。由于空格符也是一个字符，所以在串G=“abc defghne”中包含有子串“c def”,而串 “cd

4、ef”不是串G的子串。串G中第一个字符e的位置是6，第二个字符e的位置是11。3串的比较如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。两个串A、B的比较过程是：从前往后逐个比较对应位置上的字符的ASCII码值，直到不相等或有一个字符串结束为止，此时的情况有以下几种：（1）两个串同时结束，表示A等于B；（2）A中字符的ASCII码值大于B中相应位置上字符的ASCII码值或B串结束，表示A大于B；（3）B中字符的ASCII码值大于A中相应位置上字符的ASCII码值或A串结束，表示A小于B。例如：“abc”=“abc”，“abc”“abcdefg”，“132”“123456”，“AB

5、ab”“2+3”。4空格串由一个或多个空格字符组成的串称为空格串，空格串的长度为串中所含空格字符的个数。在串操作中不要将空格串和空串混淆。4.1.2串的基本操作尽管串的定义和线性表极为相似，但是串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，比如对线性表的查找、访问、插入、删除和排序等；而在串的基本操作中，通常以串整体或串的一部分（子串）作为操作对象，比如子串的查找、截取子串、删除一个子串、插入子串和子串替换等操作。串的基本操作主要有：（1）初始化串StrAssign(&T,chars) 由字符串常量chars生成字符串T的操作。（2）串复制StrCopy(&

6、T,S) 由串S复制生成串T的操作。（3）串比较StrCompare(S,T) 若S=T返回0，ST返回正数，ST返回负数。（4）求串长度StrLength(S) 返回串S的长度。（5）串连接Concat(&T,S1,S2) 将串S1和S2连接起来生成串T的操作。（6）求子串SubString(&Sub,S,pos,len) 以串S中pos位置开始的len个字符生成子串Sub的操作。（7）串查找Index(S,T,pos) 返回子串T在S中pos个字符以后出现的位置。（8）串替换Replace(&S,T,V) 将串S中所有不重叠子串T替换为串V的操作。（9）串插入StrInsert(&S,po

7、s,T) 在串S中第pos个字符前插入串T的操作。（10）删除子串StrDelete(&S,pos,len) 删除串S中第pos个字符开始的len个字符的操作。4.2串的存储表示与实现既然串是线性表的特例，所以线性表的两种存储结构对于串也是适用的。在应用中具体选用何种存储结构与串的操作有关，比如对串进行插入和删除操作运算时选用链存储结构较好，对串进行查找和求子串运算时选用顺序存储结构较好。本章主要介绍串的3种存储表示方法：（1）串的定长顺序存储表示法（2）串的堆分配存储表示法（3）串的块链式存储表示法4.2.1串的定长顺序存储表示串的定长顺序存储表示是用一组地址连续的存储单元来存储串中的字符序

8、列。在串的定长顺序存储表示中，按照预定义的大小，为每个定长的串变量分配一个固定长度的存储区，所以可以用定长字符数组来表示。1定长顺序存储结构在C+运行环境中，定长顺序结构定义为：#includeiostream.h#includestdio.h#define MAXLEN 255 /定义串的最大长度为255typedef char SStringMAXLEN+1; /定义定长顺序存储类型SString2基本操作的C+程序实现（1）求串长度操作int Length_SS(SString S)操作返回串S中所含字符的个数，即串的长度；如果S为空串则返回0。int Length_SS(SString

9、 S) int i=0;while(Si)i+;return(i);（2）串连接操作int Concat_SS(SString &T,SString S1,SString S2)该操作将串S1、S2连接生成串T，如果在连接过程中产生了截断（即S1的长度加上S2的长度大于MAXLEN）则返回0，否则返回1。int Concat_SS(SString &T,SString S1,SString S2)int i,j,k;i=j=k=0;while(Ti+=S1j+);i-;while(iMAXLEN&(Ti=S2k) i+;k+; Ti=0;if(i=MAXLEN)&S2k) return(0);

10、 /*判断是否产生截断*/else return(1);（3）求子串操作int SubString_SS(SString &Sub,SString S,int pos,int len)该操作截取串S中从第pos个字符开始的连续的len个字符生成子串Sub，如果位置pos和长度len合理则返回1，否则返回0.int SubString_SS(SString &Sub,SString S,int pos,int len)int i=0;if(pos1|lenLength_SS(S)+1) return 0; /*判断位置和长度是否合理*/while(ilen) Subi=Si+pos-1; i+;

11、 Subi=0;return 1; （4）初始化串操作int StrAssign_SS(SString &T,char *s)该操作用字符数组s，初始化定长顺序串T。如果不产生截断（长度合理）返回1，否则返回0。int StrAssign_SS(SString &T,char *s)int i=0;while(iT则返回正数,如果S=T则返回0,否则返回负数。int StrCompare_SS(SString S,SString T)int i=0;while(Si&Ti&(Si=Ti)i+;return (int)(Si-Ti);（7）串的替换操作int Replace_SS(SString

12、 &S,int n,int m,SString T)该操作将串S中从第n个字符开始的连续的m个字符替换成串T中的字符，如果n和m的选取合理则返回1，否则返回0。int Replace_SS(SString &S,int n,int m,SString T)SString S1;int len=Length_SS(T);int i=n-1,j=0,k=n+m-1; /*i为开始替换位置，j指向第一个替换字符，k为剩余字符的开始位置*/if(n1|mLength_SS(S)+1|Length_SS(S)+len-mMAXLEN) return(0);/*判断位置是否合理*/StrCopy_SS(S

13、1,S); /*将剩余部分复制到S1中*/while(Si+=Tj+); /*替换S中指定部分的字符*/i-;while(Si+=S1k+); /*将剩余部分复制到S中*/return(1);（8）主函数演示程序main()void main_SS()SString s1,s2,s3,sub,T;char str1100,str2100;int l1,l2,l3,pos,len,n;while(1)coutstr1”不能输入空格字符（空格符表示输入结束）且对串的长度不做检查。*/cin.getline(str2,sizeof(str2);StrAssign_SS(s1,str1);StrAss

14、ign_SS(s2,str2);l1=Length_SS(s1);l2=Length_SS(s2);cout(2)求串长操作：ns1的长度=l1，s2的长度=l2endl;n=StrCompare_SS(s1,s2);cout0)couts2n;else if(n=0)couts1=s2n;else couts1s2n;Concat_SS(s3,s1,s2);cout(4)串连接操作：ns1+s2=s3endl;l3=Length_SS(s3);couts1+s2的长度=l3endl;coutposlen;if(SubString_SS(sub,s3,pos,len) coutsub=sube

15、ndl;elsecout位置不正确n; coutposlen;cout输入替换串:n;cin.get();cin.getline(str1,sizeof(str1);StrAssign_SS(T,str1);if(Replace_SS(s3,pos,len,T) cout替换结果为:ns3=s3endl;elsecout替换不成功!n;（程序运行过程略）3定长顺序存储的特点对于定长顺序存储的串在基本操作方面主要有以下特点：（1）对于求串长度和串的复制操作而言，其时间复杂度依赖于字符串的长度；（2）在串删除和串插入操作时必须移动大量的字符；（3）如果在串输入、串连接、串插入和串替换操作中串值的长

16、度超过MAXLEN，则按约定采取“截尾”法处理，这将导致操作结果的不合理。4.2.2串的堆分配存储表示由于串操作基本上是以串整体的形式参与，在应用程序中串变量的长度相差较大，并且在操作中串值长度的变化也比较大。因此，事先为串变量设置固定大小空间的数组不尽合理。用堆分配存储表示串的方法是：在程序执行过程中，根据串变量值的大小，在堆空间中动态分配一个连续的地址空间来存储串变量中的字符，这样既可以避免产生串操作中的“截断”现象又能合理使用内存空间资源。1串的堆分配存储结构在C+运行环境中，堆分配存储结构定义为struct HStringchar *ch; /串变量中字符数组的首地址int lengt

17、h; /串的长度;2在堆分配存储结构中串基本操作的C+程序实现（1）串的赋值操作void StrAssign_HS(HString &T,char str)该操作由字符串常量str生成一个HString型串T。void StrAssign_HS(HString &T,char str)int len=0,i;while(strlen)len+; /计算串的长度T.length=len;if(!len)T.ch=NULL; /对空串进行初始化elseT.ch=new charlen+1; /在堆内存中分配相应大小的存储空间for(i=0;T.chi=stri;i+); /将数据从str复制到T.

18、ch中（2）求串长的操作int Length_HS(HString S)该操作返回串S的长度，如果S为空串则返回0。int Length_HS(HString S)return(S.length); （3）串的比较操作int StrComp_HS(HString S,HString T)该操作比较串S、T的大小。int StrComp_HS(HString S,HString T)int i;for(i=0;iT.length&iS.length;i+)if(S.chi!=T.chi)break;return(int)(S.chi-T.chi);（4）串的清空操作void ClearStrin

19、g_HS(HString &S)该操作清空串S所占的堆空间。void ClearString_HS(HString &S)if(S.ch)deleteS.ch;S.ch=NULL;S.length=0;（5）串的连接操作void Concat_HS(HString &T,HString S1,HString S2)该操作计算串S1、S2的连接串T。void Concat_HS(HString &T,HString S1,HString S2)int i,j,k;T.length=S1.length+S2.length;i=j=k=0;T.ch=new charT.length+1; /分配链接

20、串的储存空间while(T.chi+=S1.chj+); /将S1复制到Ti-;while(T.chi+=S2.chk+); /将S2连接到T的末尾（6）求子串的算法int SubString_HS(HString &Sub,HString S,int pos,int len)该操作求串S中pos个字符开始的len个字符组成的子串Sub，如果位置合理返回1否则返回0。int SubString_HS(HString &Sub,HString S,int pos,int len)int i;if(pos1|lenS.length+1)return(0); /如果位置不合理时返回0值Sub.ch=

21、new charlen+1; /动态分配子串的存储空间Sub.length=len;for(i=0;ilen;i+)Sub.chi=S.chpos+i-1; /将子串复制到Sub中Sub.chi=0;return(1);（7）串插入操作的算法int StrInsert_HS(HString &S,int pos,HString H)该操作在串S的第pos个字符前面插入字符串H，如果位置合理返回1，否则返回0。int StrInsert_HS(HString &S,int pos,HString H)int i,j,k;HString S1;if(posS.length+1)return 0;

22、/位置不合理返回0值S1.length=S.length+H.length;S1.ch=new charS1.length+1; /重新分配空间for(i=0;ipos-1;i+)S1.chi=S.chi; /取S中pos前段内容k=i;for(j=0;j H.length;j+)S1.chi+=H.chj; /将H插入while(S1.chi+=S.chk+); /取S中剩余的内容deleteS.ch;S=S1;return 1;（8）串替换操作的算法int Replace_HS(HString &S,int n,int m,HString T)该操作将串S中第n个字符开始的m个字符替换为串

23、T，如果位置n和字符数m合理返回1否则返回0。int Replace_HS(HString &S,int n,int m,HString T)int i,j,k=n+m-1;HString S1; if(n1|mS.length+1)return(0); /长度或位置不合理S1.length=S.length+T.length-m;S1.ch=new charS1.length+1; /重新分配储存空间 for(i=0;in-1;i+)S1.chi=S.chi; /取S中前面的部分for(j=0;jT.length;j+)S1.chi+=T.chj; /取T中的内容while(S1.chi+=

24、S.chk+); /取S中剩余的部分deleteS.ch;S=S1;return(1);（9）主函数演示程序main()void main_HS()HString S1,S2,S,sub,V,T;SString ss1,ss2;int n,pos,len;while(1)cout(1)串初始化操作：n输入两个字符串:n;cin.getline(ss1,sizeof(ss1);cin.getline(ss2,sizeof(ss2);StrAssign_HS(S1,ss1);StrAssign_HS(S2,ss2);cout(2)求串长操作：nlen1=Length_HS(S1)endl;cout

25、len2=Length_HS(S2)endl;cout0)coutS2n;else if(n0)coutS1S2n;elsecoutS1=S2n;Concat_HS(S,S1,S2);cout(4)串连接操作：n:s1+s2=S.chendl; coutlength=Length_HS(S)endl;coutposlen;if(SubString_HS(sub,S,pos,len) coutsub=sub.chendl;else cout位置不对!n;coutpos;cin.get();cout输入要插入的子串V:n;cin.getline(ss1,sizeof(ss1);StrAssign_

26、HS(V,ss1);if(StrInsert_HS(S,pos,V) cout插入结果为 s=S.chendl;elsecout位置不对!n;coutposlen;cin.get();cout输入替换串T:n;cin.getline(ss1,sizeof(ss1);StrAssign_HS(T,ss1); if(Replace_HS(S,pos,len,T) cout结果为 s=S.chendl;elsecout位置不对!n;3堆分配存储表示的特点从以上串基本操作的算法可以看出，堆分配存储结构的串既有顺序存储结构的特点，处理方便，同时在操作中对串的长度又没有任何限制，更显灵活，因此该存储结构在

27、有关字符串处理的应用程序中常被采用。4.2.3串的块链式存储表示1块链式存储的概念和线性表的链式存储结构类似，可以采用链表方式存储串。由于串中的每个数据元素是一个字符，在用链表存储串值时，存在一个“结点大小”的问题，即每个结点最多可以存放多少个串中字符。对于串“abcdefghijk”，如果采用每个结点存放一个字符的链表结构存储，其存储方式如图4.1(a)所示；如果采用每个结点存放三个字符的链表结构存储，其存储方式如图4.1(b)所示。由于串长不一定是结点大小的整数倍，所以在链表的最后一个结点不一定能被串中的字符占满，此时可补上若干个非串值字符#（或其它非串值字符）。为了便于进行串的操作，当以

28、链表存储串值时，除了头指针head外还可以附设一个指向尾结点的指针tail，并给出当前串的长度。称如此定义的串的存储结构为串的块链式存储结构。2块链式存储结构的表示在C+运行环境中，可将块链式存储结构表示如下：#define CHUNKSIZE 80 /定义每个结点的大小struct Chunk char chCHUNKSIZE; /块内的字符数组 Chunk* next; /指向下一个结点的指针; /块结构的类型定义struct LString Chunk *head,*tail; /串的头指针和尾指针 int curlen; /串的长度; /块链式结构的类型定义在一般情况下，对串的操作只需

29、要从前向后扫描即可，故对串值不必建立双向链表。设尾指针的目的是为了便于进行串的连接操作，在串连接时需要处理第一个串尾结点中的无效字符。3块链式存储的存储密度在串的块链式存储结构中，结点大小的选择很重要，它直接影响到串处理操作的效率。如果块选取的充分大时（可在一个块中存储串的所有字符）即为定长存储；如果每个块只放一个字符时即为链表存储。为了便于研究串值的存储效率我们给出如下存储密度的计算公式：假定next指针变量占用4个字节，每个字符占用1个字节，每个块中存放m个字符，那么串值的存储密度可以表示为=m/(m+4)。显然，存储密度小（比如每个块存放1个字符时=20%），运算处理方便，但是存储占用量

30、大；存储密度大（比如每个块存放80个字符时=20/21=95%），虽然存储占用量小，但是串值的运算处理（比如串的插入、删除、连接和替换等操作）不太方便。4块链式存储表示的特点在一般情况下，对以块链式存储表示的串进行操作时比较麻烦，比如在串中插入一个子串时可能需要分割结点，连接两个串时，如果第一个串的最后一个结点没有填满，还需要添加其它字符。总的来说，用链表作为串的存储方式是不太实用的。因此，串的块链式存储结构不如定长顺序存储和堆分配存储结构灵活，它占用存储空间大且操作复杂。4.3串的模式匹配设S和T是两个给定的串，在串S中寻找串值等于T的子串的过程称为模式匹配。其中，串S称为主串，串T称为模式

31、。如果在串S中找到等于串T的子串，则称匹配成功；否则匹配失败。模式匹配是各种串处理系统中最重要的操作之一。模式匹配的操作记为Index(S,T,pos)，该函数的功能是，从串S的第pos个字符开始的字符序列中查找值等于T的子字符串。如果匹配成功，函数返回T在S中第pos个字符以后的串值中第一次出现的开始位置；否则函数返回0值。显然这里隐含要求模式串T不能为空串。4.3.1串模式匹配的BF算法在串的模式匹配算法中，最简单、最直观的算法是BF（Brute-Force,布鲁特-福斯）算法，在该算法中，分别利用指针i和指针j指示主串S和模式T中当前正待比较的字符下标。算法的基本思想是：从主串S的第po

32、s个字符起和模式T的第一个字符比较，若相等，则继续逐个比较后面的字符；否则从主串S的下一个字符起再重新和模式T的第一个字符开始逐个比较。以此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数返回T的第一个字符在S中的位置，否则匹配不成功，函数返回0值。BF算法表示的串查找函数int IndexBF_SS(SString S,SString T,int pos)的C+语言表示为：int IndexBF_SS(SString S,SString T,int pos=1)/求子串T在S中从pos个位置开始首次出现的位置int i=pos-1,j=0;if(iLen

33、gth_SS(S)+1)return(0);while(Si+j&Tj)if(Si+j=Tj)j+; /若字符相等，则继续比较后续字符elsei+;j=0; /若不相等，则重新开始新一轮比较if(!Tj) return(i+1); /若匹配成功，则返回T首次出现的开始位置else return(0); /若匹配不成功，则返回0算法分析：在一般情况下，BF算法的时间复杂度为O(m+n)，其中m,n分别为串S和T的长度。但是在有些情况下，该算法的效率很低。例如：S=“aaaaaaaaaaab”共有52个a和1个b,T=“aaaaaaab”共有7个a和1个b。由于每趟比较都是在最后一个字符出现不相等

34、，此时需要将初始位置指针i回溯到i+1的位置上，并从模式的第一个字符开始重新比较。从图4.2所示的匹配过程可以直观地算出，初始位置指针i一共要回溯52-7=45次，总的比较次数为：8(45+1)=368次。所以，在最坏的情况下BF算法的时间复杂度为O(mn)。4.3.2模式匹配的KMP算法模式匹配的另一种算法是由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的，称之为克努特-莫里斯-普拉特操作，简称KMP算法，他是一种改进的模式匹配算法。此算法可使时间复杂度在O(m+n)的数量级上完成串的模式匹配操作。1模式的next数组模式匹配的KMP算法是，每当一趟匹配比较过程中出现

35、字符不相同的情况时，不需要回溯指针i,而是利用已经得到的“部分匹配”的结果将模式T向右“滑动”尽可能远的一段距离后，再继续进行比较。为此需要引入一个有关模式串T的整型数组next，其中第j个元素nextj-1表示当模式串T中的第j个字符与主串S中相应字符匹配失败时，在模式T中需要重新和主串S中该字符进行比较的字符的下标值。next数组定义为：其中nextj=k表明，存在整数k满足条件0kj，并且在模式T中存在下列关系：“T0T1Tk-1”=“Tj-kTj-k+1Tj-1”，而对任意的整数k1(0kk1j)都有：“T0T1Tk1-1”“Tj-k1Tj-k1+1Tj-1”例如：（1）模式T=“aa

36、aaaaab”的next数组为next=-1,0,1,2,3,4,5,6（2）模式T=“abaabcac”的next数组为next=-1,0,0,1,1,2,0,1（3）模式T=“ababcabcacbab”的next数组为next=-1,0,0,1,2,0,1,2,0,1,0,0,12next数组的算法实现由定义可知，next0=-1,next1=0，假设现已求得next0,next1, ,nextj,那么可以采用以下递推的方法求出nextj+1。令k=nextj，（1）如果k=-1或Tj=Tk,则转入步骤(3)（2）取k=nextk,再重复操作(1)、(2)（3）nextj+1=k+1;计

37、算next数组的算法void GetNext(char* T,int* next)用C+语言实现如下void GetNext(char* T,int* next)int i=0,k=-1,n=0;next0=-1;while(Tn)n+; /计算模式串T的长度nwhile(in-1)if(k=-1|Ti=Tk)next+i=+k;elsek=nextk;void main()char p650=ababcabcacbab,abaabcac,aaabcaab,abcabca,babbabab,abcaabbabcabaac;int next50,i,j;for(i=0;i6;i+)GetNext

38、(pi,next); /计算模式串pi的next数组for(j=0;pij;j+)coutnextj ; /显示输出pi的next数组coutendl;运行结果为：-.23.-1 0 0 1 2 0 1 2 0 1 0 0 1-1 0 0 1 1 2 0 1-1 0 1 2 0 0 1 2-1 0 0 0 1 2 3-1 0 0 1 1 2 3 2-1 0 0 0 1 1 2 0 1 2 3 4 2 1 13KMP模式匹配算法的比较过程假设主串为S=“aaaaaaaaaaab”（其中共有52个a和1个b），模式串为T=“aaaaaaab”（其中共有7个a和1个b）。下面给出KMP模式匹配算法的

39、比较过程：首先求得模式T的next数组为next=-1,0,1,2,3,4,5,6，主串与模式串的字符下标初值为i=0,j=0。(1) 连续比较8次时，i=7,j=7，此时分别指向S的第8个a和T中最后的b；即SiTj。 (2) 取j为nextj=next7的值6，即j=6指向T中第7个a(表示模式T向后滑动7-6=1个字符)。(3) 比较Si和Tj，均为a相同，i+,j+。(4) 此时i的值+1,j=7，分别指向S的下一个a和T中最后的b；即SiTj，转入（2）继续。(5) 重复(2)、(3)、(4)的步骤52-7=45次后，i、j均指向最后的字符b,即Si=Tj。(6) i+,j+操作后j

40、=m(m为T的长度8)，循环结束，返回i-m+1。从以上分析的比较过程可知，总的比较次数为：7+2(52-7)+1=98次（见图4.3）再如：主串为S=“abcdabcdabcdabcde”，模式串为T=“abcde”,则next=-1,0,0,0,0。那么，可以算出用BF算法时的比较次数为29次。而用KMP算法的比较过程为：(1) 比较5次后滑动模式T:j=next4=0,即向右滑动4个字符，此时j=0,i=4；(2) 再次连续比较5次后将模式T向右滑动4个字符，此时j=0,i=9；以此类推，共需要比较的次数为54=20次（见图4.4）。4KMP模式匹配算法的实现KMP模式匹配算法int I

41、ndex_KMP(SString S,SString T,int pos)的C+语言实现int Index_KMP(SString S,SString T,int pos=1)int i=pos-1,j=0; /i指向S中第一个比较字符，j指向T中第一个字符int m=Length_SS(T), n=Length_SS(S);int *next=new intm; /定义模式T的next数组if(in+1)return 0; /位置不合理返回0值GetNext(T,next); /计算next while(in&j=m) return(i-m+1); /匹配成功else return(0);v

42、oid main()SString S,T;int pos,n;coutS;coutT;coutpos;if(n=Index_KMP(S,T,pos)cout首次匹配地址为:nendl;else coutLength_SS(S)return(0);while(Si+j&Tj)num+;if(Si+j=Tj)j+; /若字符相等，则继续比较后续字符elsei+;j=0; /若不相等，则重新开始新一轮比较if(!Tj) return(i+1); /若匹配成功，则返回T首次出现的开始位置else return(0); /若匹配不成功，则返回0（2）函数int IndexKMP(SString S,S

43、String T,int& num)的功能是通过KMP算法返回串T在S中首次出现的位置，参数num表示匹配过程中字符元素的比较次数。int IndexKMP(SString S,SString T,int& num)int i=0,j=0; /i指向S中第一个比较字符，j指向T中第一个字符int m=Length_SS(T), n=Length_SS(S);int *next=new intm; /定义模式T的next数组if(mn)return 0; /匹配不成功返回0值GetNext(T,next); /计算next num=0;while(in&j=m) return(i-m+1); /

44、匹配成功else return(0);void main()SString S,T;int n1,n2,num1,num2;while(1)coutinput string S:n;cin.getline(S,sizeof(S);coutinput string T:n;cin.getline(T,sizeof(T);n1=IndexBF(S,T,num1);n2=IndexKMP(S,T,num2);coutIndex_BF:nn=n1,num=num1endl;coutIndex_KMP:nn=n2,num=num2endl;程序运行结果为：input string S:aaaaaaaaa

45、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabinput string T:aaaaaaabIndex_BF:n=46,num=368Index_KMP:n=46,num=98input string S:abcdabcdabcdabcdeinput string T:abcdeIndex_BF:n=13,num=29Index_KMP:n=13,num=20input string S:ADBADABBAABADABBADADAinput string T:ADABBADADAIndex_BF:n=12,num=32Index_KMP:n=12,num=254.4应用举例【例4.2】应用BF模式匹配函数IndexBF_SS(S,T,pos)实现算法：int Replace_S(SString &S,SString T,SString V)该函数的功能是，将定长存储串S中的所有子串T