《第4章串》习题解答分析

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

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

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

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

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

6、opy(&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) 串插入StrIn

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

8、连续的存储单元来存储串中的字符序列。在串的定 长顺序存储表示中，按照预定义的大小，为每个定长的串变量分配一个固定长度的存储区， 所以可以用定长字符数组来表示。1 .定长顺序存储结构在C+运行环境中，定长顺序结构定义为:#i ncludeiostream.h/定义串的最大长度为255/定义定长顺序存储类型SString#i ncludestdio.h#defi ne MAXLEN 255typedef char SStri ngMAXLEN+1;2 基本操作的C+程序实现(1) 求串长度操作 int Len gth_SS(SStri ng S)操作返回串S中所含字符的个数，即串的长度；如果S为空

9、串则返回0。int Len gth_SS(SStri ng S) int i=0;while(Si)i+;return(i);(2) 串连接操作 int Con cat_SS(SStri ng &T,SStri ng S1,SStri ng S2)该操作将串S1、S2连接生成串T,如果在连接过程中产生了截断(即 S1的长度加上S2 的长度大于 MAXLEN )则返回0,否则返回1。int Con cat_SS(SStri ng &T,SStri ng S1,SStri ng S2)int i,j,k;i=j=k=0;while(Ti+=S1j+);i-;while(iMAXLE N&(Ti=S

10、2k) i+;k+; Ti=0;if(i=MAXLEN)&S2k) return(0);/* 判断是否产生截断 */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(posLength_SS(S)+1) return 0;/* 判

11、断位置和长度是否合理 */while(ilen) Subi=Si+pos-1; i+; Subi=O：return 1;(4) 初始化串操作 int StrAssign_SS(SStri ng &T,char *s)该操作用字符数组s,初始化定长顺序串T。如果不产生截断(长度合理)返回 1,否则返回0。int StrAssign_SS(SStri ng &T,char *s)int i=0;while(iT则返回正数，如果S=T则返回0,否则返回负数。int StrCompare_SS(SStri ng S,SStri ng T)int i=0;while(Si&Ti &(Si=Ti)i+;r

12、eturn (i nt)(Si-Ti);(7) 串的替换操作 int Replace_SS(SString &S,int n,int m,SString T)该操作将串S中从第n个字符开始的连续的m个字符替换成串T中的字符，如果n和m的选取合理则返回1,否则返回0oint Replace_SS(SStri ng & S,i nt n,i nt m,SStri ng T)SStri ng S1;int len=Le ngth_SS(T);int i=n-1,j=0,k =n+m-1;/*i为开始替换位置，j指向第一个替换字符，k为剩余字符的开始位置*/if(n 1|mLe ngth_SS(S)+

13、1|Le ngth_SS(S)+le n-mMAXLEN) return(O)/*判断位置是否合理*/StrCopy_SS(S1,S); while(Si+=Tj+);i-;while(Si+=S1k+); return(1);(8 )主函数演示程序mai n()/*将剩余部分复制到S1中*/*替换S中指定部分的字符*/*将剩余部分复制到S中*/void main_SS()SString s1,s2,s3,sub,T; char str1100,str2100;int I1,l2,l3,pos,le n,n;while(1) cout(1)串初始化操作：n输入两个字符串:n; cin .get

14、li ne(str1,sizeof(str1);/*表示从键盘输入一个可以含有空格字符的长度小于100的字符串到str1中，语句“cinstr1 ”不能输入空格字符(空格符表示输入结束)且对串的长度不做检查。*/cin. getl in e(str2,sizeof(str2);StrAssign_SS(s1,str1); StrAssign_SS(s2,str2); l1=Le ngth_SS(s1); l2=Le ngth_SS(s2); cout(2)求串长操作：ns1 的长度=l1 ， s2 的长度=l2endl; n=StrCompare_SS(s1,s2);cout0)couts2n

15、;else if(n=0)couts 1=s2n; else couts1s2n;Co ncat_SS(s3,s1,s2); cout(4)串连接操作：ns1+s2=s3endl;l3=Le ngth_SS(s3); couts1+s2 的长度=l3endl; cout posle n;if(SubString_SS(sub,s3,pos,len) coutsub=subendl;else cout位置不正确n; cout posle n;cout输入替换串:n; cin.get();cin .getli ne(str1,sizeof(str1);StrAssign_SS(T,str1); i

16、f(Replace_SS(s3,pos,len,T) cout替换结果为:ns3=s3endl; else cout替换不成功!n;(程序运行过程略)3 定长顺序存储的特点对于定长顺序存储的串在基本操作方面主要有以下特点：(1) 对于求串长度和串的复制操作而言，其时间复杂度依赖于字符串的长度；(2) 在串删除和串插入操作时必须移动大量的字符；(3) 如果在串输入、串连接、串插入和串替换操作中串值的长度超过MAXLEN则按约定 采取“截尾”法处理，这将导致操作结果的不合理。4.2.2串的堆分配存储表示由于串操作基本上是以串整体的形式参与，在应用程序中串变量的长度相差较大，并且 在操作中串值长度的

17、变化也比较大。因此，事先为串变量设置固定大小空间的数组不尽合理。用堆分配存储表示串的方法是：在程序执行过程中，根据串变量值的大小，在堆空间中动态分配一个连续的地址空间来 存储串变量中的字符，这样既可以避免产生串操作中的“截断”现象又能合理使用内存空间 资源。1. 串的堆分配存储结构在C+运行环境中，堆分配存储结构定义为struct HStri ng char *ch;/串变量中字符数组的首地址int length;/串的长度;2 在堆分配存储结构中串基本操作的C+程序实现(1) 串的赋值操作 void StrAssign_HS(HString &T,char str)该操作由字符串常量 str

18、生成一个HString型串T。void StrAssig n_ HS(HStri ng &T,char str) int len=0,i;while(strlen)len+;/ 计算串的长度T.len gth=le n;if(!len)T.ch=NULL;对空串进行初始化elseT.ch=new charle n+1;/在堆内存中分配相应大小的存储空间for(i=0;T.chi=stri;i+);/ 将数据从 str 复制到 T.ch 中(2) 求串长的操作 int Len gth_HS(HStri ng S)该操作返回串S的长度，如果S为空串则返回0。in t Len gth_HS(HStr

19、i ng S)return(S.le ngth); (3) 串的比较操作 int StrComp_HS(HStri ng S,HStri ng T)该操作比较串S、T的大小。int StrComp_HS(HString S,HString T) int i;for(i=0;iT.le ngth&i S.le ngth;i+) if(S.chi!=T.chi)break;return(i nt)(S.chi-T.chi);(4) 串的清空操作 void ClearStri ng_HS(HStri ng &S)该操作清空串S所占的堆空间。void ClearStri ng_ HS(HStri ng

20、 &S) if(S.ch) deleteS.ch; S.ch=NULL;S.le ngth=0;(5) 串的连接操作 void Co ncat_HS(HStri ng &T,HStri ng S1,HStri ng S2)该操作计算串S1、S2的连接串T。void Con cat_HS(HStri ng &T,HStri ng S1,HStri ng S2)int i,j,k;T.le ngth=S1.le ngth+S2.le ngth; i=j=k=0;/分配链接串的储存空间/将S1复制到T/将 S2连接到T的末尾T.ch=new charT .len gth+1;while(T.chi+

21、=S1.chj+);i-;while(T.chi+=S2.chk+);(6) 求子串的算法 int SubStri ng_ HS(HStri ng & Sub,HStri ng S,i nt pos,i nt len)该操作求串S中pos个字符开始的len个字符组成的子串Sub,如果位置合理返回1否则返回0。int SubString_HS(HString &Sub,HString S,int pos,int len)int i;if(posS.le ngth+1)return(0);如果位置不合理时返回0 值Sub.ch=new charle n+1;动态分配子串的存储空间Sub.len g

22、th=le n;for(i=0;ilen;i+)Sub.chi=S.chpos+i-1;/将子串复制到 Sub 中Sub.chi=0;return(1);(7) 串插入操作的算法int StrI nsert_HS(HStri ng &S,i nt pos,HStri ng H)H，如果位置合理返回1,否则返回0。/位置不合理返回o值/重新分配空间/取S中pos前段内容将H插入/取S中剩余的内容该操作在串S的第pos个字符前面插入字符串int StrI nsert_HS(HStri ng &S,in t pos,HStri ng H) int i,j,k;HStri ng S1;if(posS.

23、le ngth+1) return 0;S1.le ngth=S.le ngth+H.le ngth;S1.ch=new charS1.le ngth+1;for(i=0;ipos-1;i+)S1.chi=S.chi;k=i;for(j=0;j H.le ngth;j+)S1.chi+=H.chj;while(S1.chi+=S.chk+);deleteS.ch;S=S1;return 1;(8) 串替换操作的算法 int Replace_HS(HStri ng &S,i nt n,i nt m,HStri ng T)该操作将串S中第n个字符开始的 m个字符替换为串T,如果位置n和字符数m合理

24、返 回1否则返回0。int Replace_HS(HString &S,int n,int m,HString T)int i,j,k=n+m-1;HStri ng S1;if(* 1|mS.le ngth+1)return(0);/ 长度或位置不合理/重新分配储存空间/取S中前面的部分/取T中的内容/取S中剩余的部分Sl.le ngth=S.le ngth+T.le ngth-m;S1.ch=new charS1.le ngth+1;for(i=0;i n-1;i+)S1.chi=S.chi;for(j=0;jT.le ngth;j+)S1.chi+=T.chj;while(S1.chi+=

25、S.chk+);deleteS.ch;S=S1;return(1);(9 )主函数演示程序 mai n()void main_HS()HStri ng S1,S2,S,sub,V,T;SStri ng ss1,ss2;int n, pos,le n;while(1)cout(1)串初始化操作：n输入两个字符串:n;cin. getl in e(ss1,sizeof(ss1);cin. getl in e(ss2,sizeof(ss2);StrAssign_HS(S1,ss1);StrAssign_HS(S2,ss2);cout(2)求串长操作：nlen仁Length_HS(S1)endl; c

26、outle n2=Le ngth_HS(S2)e ndl;cout0)coutS2n;else if(n 0)coutS1S2n;else coutS 1=S2in;Con cat_HS(S,S1,S2);cout(4)串连接操作：n:s1+s2=S.chendl;coutle ngth=Le ngth_HS(S)e ndl;cout posle n;if(SubString_HS(sub,S,pos,len) coutsub=sub.chendl;elsecout位置不对!n;coutpos;cin.get(); cout输入要插入的子串V:n; cin.getline(ss1,sizeof

27、(ss1);StrAssign_HS(V ,ss1);if(StrInsert_HS(S,pos,V) cout插入结果为 s=S.chendl;elsecout位置不对！n;cout posle n;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 .堆分配存储表示的特点从以上串基本操作的算法可以看出，堆分配存储结构的串既有顺序存储结构的特点，处 理方便，同时在操作中对

28、串的长度又没有任何限制，更显灵活，因此该存储结构在有关字符 串处理的应用程序中常被采用。4.2.3串的块链式存储表示1 块链式存储的概念和线性表的链式存储结构类似，可以采用链表方式存储串。由于串中的每个数据元素是 一个字符，在用链表存储串值时，存在一个“结点大小”的问题，即每个结点最多可以存放 多少个串中字符。对于串“abcdefghijk ”，如果采用每个结点存放一个字符的链表结构存储,其存储方式如图4.1(a)所示；如果采用每个结点存放三个字符的链表结构存储，其存储方式如 图4.1(b)所示。由于串长不一定是结点大小的整数倍，所以在链表的最后一个结点不一定能被 串中的字符占满，此时可补上若

29、干个非串值字符#(或其它非串值字符)。结点大小为1亍宇符的樋表he屛一 | |卜斗环4|血|卜|和卜匕韶0)结点犬小为外字符的链表为了便于进行串的操作，当以链表存储串值时，除了头指针head外还可以附设一个指向尾结点的指针tail，并给出当前串的长度。称如此定义的串的存储结构为串的块链式存储结构2 块链式存储结构的表示在C+运行环境中，可将块链式存储结构表示如下:#defi ne CHUNKSIZE 80/定义每个结点的大小struct Chu nkchar chCHUNKSIZE;Chu nk* n ext;/块内的字符数组/指向下一个结点的指针/块结构的类型定义struct LStri n

30、gChu nk *head,*tail;intcurle n;/串的头指针和尾指针/串的长度/块链式结构的类型定义在一般情况下，对串的操作只需要从前向后扫描即可，故对串值不必建立双向链表。设 尾指针的目的是为了便于进行串的连接操作，在串连接时需要处理第一个串尾结点中的无效 字符。3 .块链式存储的存储密度在串的块链式存储结构中，结点大小的选择很重要，它直接影响到串处理操作的效率。 如果块选取的充分大时（可在一个块中存储串的所有字符）即为定长存储；如果每个块只放 一个字符时即为链表存储。为了便于研究串值的存储效率我们给出如下存储密度的计算公式:串值的存储密度串值所占的存储位 实际分配的存储位假定

31、next指针变量占用4个字节，每个字符占用1个字节，每个块中存放 m个字符，那么串值的存储密度可以表示为p =m/（m+4）。显然，存储密度小（比如每个块存放1个字符时P =20%,运算处理方便，但是存储占用量大；存储密度大（比如每个块存放80个字符时p=20/2仁95%）,虽然存储占用量小，但是串值的运算处理（比如串的插入、删除、连接和替换 等操作）不太方便。4 块链式存储表示的特点在一般情况下，对以块链式存储表示的串进行操作时比较麻烦，比如在串中插入一个子 串时可能需要分割结点，连接两个串时，如果第一个串的最后一个结点没有填满，还需要添 加其它字符。总的来说，用链表作为串的存储方式是不太实

32、用的。因此，串的块链式存储结构不如定长顺序存储和堆分配存储结构灵活，它占用存储空间大且操作复杂。4.3串的模式匹配设S和T是两个给定的串， 在串S中寻找串值等于 T的子串的过程称为 模式匹配。其中， 串S称为主串，串T称为模式。如果在串S中找到等于串T的子串，则称 匹配成功；否则匹 配失败。模式匹配是各种串处理系统中最重要的操作之一。模式匹配的操作记为 Index（S,T,pos），该函数的功能是，从串 S的第pos个字符开始的字 符序列中查找值等于 T的子字符串。如果匹配成功，函数返回 T在S中第pos个字符以后的 串值中第一次出现的开始位置；否则函数返回0值。显然这里隐含要求模式串 T不能

33、为空串。4.3.1串模式匹配的BF算法在串的模式匹配算法中，最简单、最直观的算法是BF （ Brute-Force,布鲁特-福斯）算法，在该算法中，分别利用指针i和指针j指示主串S和模式T中当前正待比较的字符下标。算法的基本思想是：从主串S的第pos个字符起和模式 T的第一个字符比较，若相等， 则继续逐个比较后面的字符；否则从主串S的下一个字符起再重新和模式T的第一个字符开始逐个比较。以此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数返回T的第一个字符在 S中的位置，否则匹配不成功，函数返回0值。BF算法表示的串查找函数intlndexBF_SS(SSt

34、ring 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(iLength_SS(S)+1) return(0); while(Si+j &Tj)if(Si+j=Tj)j+;else i+;j=0;if(!Tj)return(i+1);elsereturn(0);/若字符相等，则继续比较后续字符/若不相等，则重新开始新一轮比较/若匹配成功，则返回 T首次出现的开始位置/若匹配不成功，则返回0算法分析:在一般情况下

35、，BF算法的时间复杂度为 0(m+n)，其中m,n分别为串S和T的长度。但 是在有些情况下，该算法的效率很低。例如：S= aaaaaaaaaaab共有 52 个 a和 1 个 b,T= aaaaaaab共有 7 个 a和 1 个 b由于每趟比较都是在最后一个字符出现不相等，此时需要将初始位置指针i回溯到i+1的位置上，并从模式的第一个字符开始重新比较。从图4.2所示的匹配过程可以直观地算出，初始位置指针i 一共要回溯52-7=45次，总的比较次数为：8 X (45+1)=368次。所以，在最坏的情况 下BF算法的时间复杂度为 0(m X n)。扌旨针 i 对应宇符0B6038803860388

36、008B. . . 80的比较次数:j員式串：二“玄玄电也色也电匕图4卫BF算法中模盍匹配过抿飾比较次数4.3.2模式匹配的KMP算法模式匹配的另一种算法是由D.E.KnuthJH.Morris和V.R.Pratt同时发现的，称之为克努特-莫里斯-普拉特操作，简称 KMP算法，他是一种改进的模式匹配算法。此算法可使时间复杂 度在O(m+n)的数量级上完成串的模式匹配操作。1 .模式的next数组模式匹配的KMP算法是，每当一趟匹配比较过程中出现字符不相同的情况时，不需要回溯指针i,而是利用已经得到的“部分匹配”的结果将模式T向右“滑动”尽可能远的一段距离后，再继续进行比较。为此需要引入一个有关

37、模式串T的整型数组next,其中第j个元素nextj-1表示当模式串T中的第j个字符与主串S中相应字符匹配失败时，在模式 T中需要重新和主 串S中该字符进行比较的字符的下标值。next数组定义为：-1当j寸nex( j= maxk | 0 c k c j 且 T0,T1, |)|,Tk-1 = Tj-k,Tj-k +1| ,Tj-1Q 其它情况其中nextj=k表明，存在整数k满足条件0kj，并且在模式T中存在下列关系：T0T1Tk-1 ”= Tj-kTj-k+1Tj-1 ”，而对任意的整数 ki(okkij)都有：T0T1Tki-1”M Tj-kiTj-k i+1Tj-1 ”例如：(1) 模

38、式 T= aaaaaaab 的 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,12. next数组的算法实现由定义可知，next0=-1,next1=0，假设现已求得next0,next1,nextj, 那么可以采用以下递推的方法求出nextj+1。令 k=nextj,(1)如果k=-1或Tj=Tk,则转入步骤(3)(2 )取 k=nextk,再重复操

39、作(1)、(2)(3) n extj+1=k+1;计算next数组的算法 void GetNext(char* T,int* next)用C+语言实现如下void GetNext(char* T,int* next)int i=0,k=-1, n=0;n ext0=-1;while(Tn)n+;/计算模式串T的长度nwhile(i n-1)if(k=-1|Ti=Tk)n ext+i=+k;elsek=n extk;void mai n()char p650=ababcabcacbab,abaabcac,aaabcaab,abcabca,babbabab,abcaabbabcabaac;int

40、n ext50,i,j;for(i=0;i6;i+)GetNext(pi,next);计算模式串 pi的 next 数组for(j=0;pij;j+)coutnextj ;/显示输出 pi的 next 数组coute ndl;运行结果为：-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 1-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 23. KMP模式匹配算法的比较过程假设主串为 S= aaaaaaaaaaab(其中共有 52个a和1个b,模式串为 T= aa

41、aaaaab(其中共有7个a和1个b)。下面给出KMP模式匹配算法的比较过程：首先求得模式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即Si工Tj。(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即Si丰Tj，转入(2) 继续。(5) 重复、(3)、的步骤52-7=45次后

42、，i、j均指向最后的字符b,即Si=Tj。(6) i+,j+操作后j=m(m为T的长度8)，循环结束，返回i-m+1。从以上分析的比较过程可知，总的比较次数为：7+2 X (52-7)+1=98次(见图4.3 )$貝式串：T二也也迪包玄乳吉ne黑二-14*56主串：二电岂岂岂电包玄岂电岂岂玄电令玄岂，a电令玄岂电aab匕匕较次数：1111111監2222222 匹22監221E4.3 KMP算法中梯式匹配迅理的此綾次数再如：主串为 S= “abcdabcdabcdabcde” 模式串为 T= “abcde”则 next=-1,0,0,0,0。那么, 可以算出用BF算法时的比较次数为 29次。而

43、用KMP算法的比较过程为：(1) 比较5次后滑动模式 T:j=next4=0,即向右滑动4个字符，此时j=0,i=4 ;(2) 再次连续比较5次后将模式T向右滑动4个字符，此时j=0,i=9 ;以此类推，共需要比较的次数为5X4=20次(见图4.4) o複式：T二第H朕：心t卜卜型 主串值:匸恥佃c佃u佃皿“ 册篡法比较次数：包11511电1115 刖F方法比较衣数：111扭门1处】1疸1亘图4.4两种模式匹配陈法的比较4. KMP模式匹配算法的实现KMP 模式匹配算法 intlndex_KMP(SString S,SString T,int pos)的 C+ 语言实现int In dex_K

44、MP(SStri ng S,SStri ng T,i nt pos=1)int i=pos-1,j=0;i指向S中第一个比较字符，j指向T中第一个字符int m=Le ngth_SS(T), n=Le ngth_SS(S);int *n ext=new in tm; if(in+1) return 0; GetNext(T ,n ext);while(i n&j=m) return(i-m+1); else return(0);/定义模式T的next数组/位置不合理返回0值/计算next/比较后继字符回溯模式指针j/匹配成功void mai n()SStri ng S,T;S:n; cin S

45、; T:n; cin T; pos:n;ci n pos;int pos ,n;cout输入主串cout输入子串cout输入位置 if(n=I ndex_KMP(S,T,pos)cout首次匹配地址为：nendl; else coutLe ngth_SS(S) while(Si+j &Tj)nu m+;if(Si+j=Tj)j+;elsei+; j=0;if(!Tj)return(i+1);elsereturn(0);return(0);若字符相等，则继续比较后续字符/若不相等，则重新开始新一轮比较/若匹配成功，则返回 T首次出现的开始位置/若匹配不成功，则返回0(2)函数 intlndexK

46、MP(SString S,SString T,int& num) 的功能是通过 KMP 算法返回串 T 在S中首次出现的位置，参数 num表示匹配过程中字符元素的比较次数。int IndexKMP(SString S,SString T,int& num) int i=O,j=O;int m=Le ngth_SS(T), n=Le ngth_SS(S); int *n ext=new in tm;if(m n) return 0;GetNext(T ,n ext); num=O;while(i n&j=m) return(i-m+1); else return(O);void mai n()S

47、Stri ng S,T;int n1,n2,nu m1, nu m2;while(1)couti nput stri ng S:n; cin .getli ne(S,sizeof(S);coutinput string T:n; cin .getli ne(T,sizeof(T);n1=I ndexBF(S,T ,n um1); n 2=I ndexKMP(S,T, nu m2);i指向S中第一个比较字符，j指向T中第一个字符定义模式T的next数组匹配不成功返回0值/计算next/比较后继字符回溯模式指针j/匹配成功coutI ndex_BF:nn=n 1, num=nu m1e ndl;c

48、outI ndex_KMP:nn= n2, nu m= nu m2e ndl;程序运行结果为：Index_BF: n=46,num=368 Index_KMP:n=13,num=20input string S:ADBADABBAABADABBADADA/n=46,num=98 input string S:input string T: ADABBADADA /abcdabcdabcdabcde/Index_BF:input string S:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaab/input string T:aaaaa

49、aab7input string T: abcde/ Index_BF: n=13,num=29 Index_KMP:n=12,num=32n=12,num=25lndex_KMP:4.4应用举例【例4.2】应用BF模式匹配函数IndexBF_SS(S,T,pos)实现算法：int Replace_S(SStri ng & S,SStri ng T,SStri ng V)该函数的功能是，将定长存储串S中的所有子串T用定长串V来替换。如果操作成功函数返回值1,否则返回值0。算法思想假设模式串T的长度为lt，替换串V的长度为lv，先从pos=1的位置开始查找 T在S中 出现的位置n，如果操作成功，则将 S中第n个开始lt个字符替换为