数据结构 第四章(串) 考试题目

第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的（）【北方交通大学 2001 一、5（2分）】A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index (S2,‘8’),length(S2)))其结果为（）【北方交通大学 1999 一、5 （25/7分）】A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】4．已知串S=‘aaab’,其Next数组值为（）。

【西安电子科技大学 1996 一、7 （2分）】A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（）。

【中山大学 1999 一、7】A．0 B．012121111212 C．0 D．06．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999 一、1（2分）】7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。

第四章串习题4一、选择题1.串是一种分外的线性表，其分外性体现在（）。

A.可以顺序存储B.数据元素是一个字符C.可以连接存储D.数据元素可以是多个字符2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。

A.模式匹配B.联接C.求子串D.求串长3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非通俗子串（非空且例外于S本身）的个数为（）。

A.n²B.（n²/2）+（n/2）C.（n²/2）+（n/2）-1D.（n²/2）-（n/2）-14.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength（s2）），subString(s1，Strlength（s2），2)））的结果串是（）。

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF5.顺序串中，根据空间分配方式的例外，可分为（）。

A.直接分配和间接分配B.静态分配和动态分配C.顺序分配和链式分配D.随机分配和不变分配6.设串S=“abcdefgh”，则S的所有非通俗子串（除空串和S自身的串）的个数是（）。

A.8B.37C.36D.357.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。

A.O(m)B.O（n）C.O（m+n）D.O（n*m）8.已知串S=“aaab”，其next数组值为（）。

A.0123B.1123C.1231D.1211二丶填空题1.在空串和空格串中，长度不为0的是（）。

2.空格串是指（），其长度等于（）。

3.按存储结构的例外，串可分为（）、（）和（）。

4.C语言中，以字符（）表示串值的终结。

5.在块链串中，为了提高存储密度，应该增大（）。

第4章习题解答一、填空1.字符串是一种特殊的线性表，特殊在于它的数据元素只能是一字符,特殊在于串可以作为一个__________ 参与所需要的处理。

2.空格串是由___ 组成的串，空串是_________ 的串，因此空格串和空串不是一个概念。

3.字符串中任意多个_______ 字符所组成的子序列，被称作是这个串的“子串”，这个字符串木身则称为“主串”。

4.我们说两个字符串相等，在计算机内部实际上是通过对相应位置上字符__________ 码的比较而得到的结论。

5.设有串s=<t I am a teacher"。

该串的长度是_________ 。

6.设有三个串：sl=“Good", s2=9', s3=“bye!''。

则si、s2、s3连接后的结果串应该是7.所谓“数组”，是指〃(H>1)个具有」业L类型的数据的有序集合。

8.矩阵与通常所说的[维数组冇关。

9.所谓“特殊矩阵”,是指那些元素在矩阵小的分布具有一定规律性的矩阵；而矩阵小的零元素个数远远多于非零元素的个数，但非零元素的分布却没有规律，这样的矩阵被称为“稀疏矩阵”。

10.在一个阶方阵A中，若所有元素都有性质：= n),就称其为对称矩阵。

二、选择1 •设有两个串si和s20求s2在si中首次出现的位置的操作称为__________ oA.连接B.模式匹配C.求了串D.求串长2・有串：“①"，那么它的长度是____ oA. 0B. 1C. 2D. 33.设有串sl=“ABCDEFG'和s2=“PQRSF'。

已知:算法con(x, y)返回串x和y的连接串；subs(s, i, j)返回串s的第i个字符开始往后j个字符组成的子串；len(s)返回串s的长度。

那么，con(subs(sl, 2, len(s2)), subs(sl, len(s2), 2))的操作结果是串__________ 。

《数据结构与算法》第四章-串考研真题精选一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（）A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长4．已知串S=‘aaab’,其next数组值为（）。

A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（）。

A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 18．若串S=’software’,其子串的数目是（）。

吉林省专升本考试数据结构分章习题及参考答案———选择题（第四章）1、多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为( )。

A、数组的元素处在行和列两个关系中B、数组的元素必须从左到右顺序排列C、数组的元素之间存在次序关系D、数组是多维结构，内存是一维结构2、串的长度是（）A、串中不同字母的个数B、串中不同字符的个数C、串中所含字符的个数D、串中所含字符的个数，且大于03、串与普通的线性表相比较，它的特殊性体现在（）。

A、顺序的存储结构B、链式存储结构C、数据元素是一个字符D、数据元素任意4、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1……n(n+1)/2]中，则在B中确定aij(i<j)的位置k的关系为( )。

A、i*(i-1)/2+jB、j*(j-1)/2+iC、i*(i+1)/2+jD、j*(i+1)/2+i5、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A、60B、66C、18000D、336、若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是()。

A、 1086B、 1032C、 1068D、答案A,B,C都不对7、下面的说法中,不正确的是(）A、数组是一种线性结构B、数组是一种定长的线性结构C、除了插入与删除操作外，数组的基本操作还有存取修改、检索和排序等D、数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作8、设有一个n*n的对称矩A,将其下三角部分按行存放在一维数组B中，而A[0][0]存放于B[0]中，那么第i行对角线元素A[i][i]存放于B中( ) 处。

A、(i+3)i/2B、(i+1)i/2C、(2n-i+1)i/2D、(2n-i-1)i/29、设模式T=“abcabc”，则该模式的next值为（）A、{-1,0,0,1,2,3}B、{-1,0,0,0,1,2}C、{-1,0,0,1,1,2}D、{-1,0,0,0,2,3}10、下面()不属于特殊矩阵。

数据结构第四章测验一、单选题 (共100.00分)1. 以下结构中，哪一个是属于逻辑结构（）A. 顺序表B. 链栈C. 循环队列D. 串正确答案：D2. 以下哪一种是串在计算机中的常见表示方式（）A. 定长顺序B. 堆分配C. 块链D. 前三种都是正确答案：D3. 在数据结构中，串可以等同于（）的处理A. 整数串B. 浮点数串C. 字符串D. 多种类型的数组正确答案：C4. 以下哪一种是串匹配的常用算法（）A. 普里姆算法B. 克鲁斯卡尔算法C. KMP算法D. 关键路径算法正确答案：C5. 已知主串为abcbcaddabc，模式串为cad，假设串位置从1开始，则串匹配位置是（）A. 3B. 5C. 7D. 不存在正确答案：B6. 已知模式串为abaab，则next数组为（）A. 1122B. 22312C. 1212D. 1112正确答案：A7. 已知串S的内容为1+2+3，以下描述哪一个是正确的（）A. 串S的长度是6B. 串S的运算结果是6C. 整数1是串S的子串D. 符号+是串S的子串正确答案：D8. 以下描述哪一个是正确的（）A. 串是字符有限序列B. 串是整数、浮点数、字符等多种数据的有限序列C. 只包含空格的串称为空串D. 串只能使用顺序表存储正确答案：A9. 串的长度是指（）A. 串中包含不同字母的个数B. 串中所含字符的个数C. 串中包含不同字符的个数D. 串中包含非空格的字符的个数正确答案：B10. 串函数Sub(S, x, y)表示在串S中，从x位置开始，取出y个字符，串位置从1开始计算。

已知串S内容为Shenzh en，则Sub(S, 2, 3)是（）A. SheB. zhenC. ShenD. hen正确答案：D。

习题四串一、单项选择题‎1．下面关于串‎的的叙述中‎，哪一个是不‎正确的？（）A．串是字符的‎有限序列 B．空串是由空‎格构成的串‎C．模式匹配是‎串的一种重‎要运算 D．串既可以采‎用顺序存储‎，也可以采用‎链式存储2．串是一种特‎殊的线性表‎，其特殊性体‎现在（）。

A．可以顺序存‎储 B．数据元素是‎一个字符C．可以链接存‎储 D．数据元素可‎以是多个字‎符3．串的长度是‎指（）A．串中所含不‎同字母的个‎数 B．串中所含字‎符的个数C．串中所含不‎同字符的个‎数 D．串中所含非‎空格字符的‎个数4．设有两个串‎p和q，其中q是p‎的子串，求q在p中‎首次出现的‎位置的算法‎称为（）A．求子串 B．联接 C．匹配 D．求串长5．若串S=“softw‎a re”,其子串的个‎数是（）。

A．8 B．37 C．36 D．9二、填空题1．含零个字符‎的串称为_‎_____‎串。

任何串中所‎含____‎__的个数‎称为该串的‎长度。

2．空格串是指‎__ __，其长度等于‎__ __。

3．当且仅当两‎个串的__‎____相‎等并且各个‎对应位置上‎的字符都_‎_____‎时，这两个串相‎等。

一个串中任‎意个连续字‎符组成的序‎列称为该串‎的____‎__串，该串称为它‎所有子串的‎_____‎_串。

4．INDEX‎（‘DATAS‎T RUCT‎U RE’，‘STR’）=_____‎___。

5．模式串P=‘abaab‎c ac’的next‎函数值序列‎为____‎____。

6．下列程序判‎断字符串s‎是否对称，对称则返回‎1，否则返回0‎；如 f("abba")返回1，f("abab")返回0；int f((1)__ _____‎_){int i=0,j=0;while‎(s[j])(2)___ _____‎;for(j--; i<j && s[i]==s[j]; i++,j--);retur‎n((3)___ ____)}7．下列算法实‎现求采用顺‎序结构存储‎的串s和串‎t的一个最‎长公共子串‎。

第四章串4.10void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r{StrAssign(r,''); //初始化r为空串for(i=Strlen(s);i;i--){StrAssign(c,SubString(s,i,1));StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中}}//String_Reverse4.11void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r{StrAssign(r,'');for(i=1;i<=Strlen(s);i++){StrAssign(c,SubString(s,i,1));for(j=1;j<i&&StrCompare(c,SubString(s,j,1));j++); //判断s的当前字符c是否第一次出现if(i==j){for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中if(k>Strlen(t)) StrAssign(r,Concat(r,c));}}//for}//String_Subtract4.12int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数{for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串{ //分别把T的前面和后面部分保存为head和tailStrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));StrAssign(S,Concat(head,V));StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串i+=Strlen(V); //当前指针跳到插入串以后n++;}//ifreturn n;}//Replace分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?4.13int Delete_SubString(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数{for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++)if(!StrCompare(SubString(s,i,Strlen(t)),t)){StrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1));StrAssign(S,Concat(head,tail)); //把head,tail连接为新串n++;}//ifreturn n,}//Delete_SubString4.14Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new{Initstack(s); //s的元素为Stringtype类型for(i=1;i<=Strlen(str);i++){r=SubString(str,i,1);if(r为字母) push(s,r);else{if(StackEmpty(s)) return ERROR;pop(s,a);if(StackEmpty(s)) return ERROR;pop(s,b);StrAssign(t,Concat(r,b));StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b连接为新子前缀表达式cpush(s,c);}}//forpop(s,new);if(!StackEmpty(s)) return ERROR;return OK;}//NiBoLan_to_BoLan分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序.4.15void StrAssign(Stringtype &T,char chars&#;)//用字符数组chars给串T赋值,Stringtype的定义见课本{for(i=0,T[0]=0;chars[i];T[0]++,i++) T[i+1]=chars[i];}//StrAssign4.16char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数{for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);if(i>s[0]&&i>t[0]) return 0;else if(i>s[0]) return -t[i];else if(i>t[0]) return s[i];else return s[i]-t[i];}//StrCompare4.17int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数{for(n=0,i=1;i<=S[0]-T[0]+1;i++){for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);if(k>T[0]) //找到了与T匹配的子串:分三种情况处理{if(T[0]==V[0])for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换S[i+l-1]=V[l];else if(T[0]<V[0]) //新子串长度大于原子串时:先将后部右移{for(l=S[0];l>=i+T[0];l--)S[l+V[0]-T[0]]=S[l];for(l=1;l<=V[0];l++)S[i+l-1]=V[l];}else //新子串长度小于原子串时:先将后部左移{for(l=i+V[0];l<=S[0]+V[0]-T[0];l++)S[l]=S[l-V[0]+T[0]];for(l=1;l<=V[0];l++)S[i+l-1]=V[l];}S[0]=S[0]-T[0]+V[0];i+=V[0];n++;}//if}//forreturn n;}//String_Replace4.18typedef struct {char ch;int num;} mytype;void StrAnalyze(Stringtype S)//统计串S中字符的种类和个数{mytype T[MAXSIZE]; //用结构数组T存储统计结果for(i=1;i<=S[0];i++){c=S[i];j=0;while(T[j].ch&&T[j].ch!=c) j++; //查找当前字符c是否已记录过if(T[j].ch) T[j].num++;else T[j]={c,1};}//forfor(j=0;T[j].ch;j++)printf("%c: %d\n",T[j].ch,T[j].num);}//StrAnalyze4.19void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r{r[0]=0;for(i=1;i<=s[0];i++){c=s[i];for(j=1;j<i&&s[j]!=c;j++); //判断s的当前字符c是否第一次出现if(i==j){for(k=1;k<=t[0]&&t[k]!=c;k++); //判断当前字符是否包含在t中if(k>t[0]) r[++r[0]]=c;}}//for}//Subtract_String4.20int SubString_Delete(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数{for(n=0,i=1;i<=s[0]-t[0]+1;i++){for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++);if(j>m) //找到了与t匹配的子串{for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]]; //左移删除s[0]-=t[0];n++;}}//forreturn n;}//Delete_SubString4.21typedef struct{char ch;LStrNode *next;} LStrNode,*LString; //链串结构void StringAssign(LString &s,LString t)//把串t赋值给串s{s=malloc(sizeof(LStrNode));for(q=s,p=t->next;p;p=p->next){r=(LStrNode*)malloc(sizeof(LStrNode));r->ch=p->ch;q->next=r;q=r;}q->next=NULL;}//StringAssignvoid StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.{for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next){p->ch=q->ch;pre=p;}while(q){p=(LStrNode*)malloc(sizeof(LStrNode));p->ch=q->ch;pre->next=p;pre=p;}p->next=NULL;}//StringCopychar StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数{for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next);if(!p&&!q) return 0;else if(!p) return -(q->ch);else if(!q) return p->ch;else return p->ch-q->ch;}//StringCompareint StringLen(LString s)//求串s的长度(元素个数){for(i=0,p=s->next;p;p=p->next,i++);return i;}//StringLenLString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针{p=malloc(sizeof(LStrNode));for(q=p,r=s->next;r;r=r->next){q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;}//for //复制串sfor(r=t->next;r;r=r->next){q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;}//for //复制串tq->next=NULL;return p;}//ConcatLString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串{p=malloc(sizeof(LStrNode));q=p;for(r=s;start;start--,r=r->next); //找到start所对应的结点指针rfor(i=1;i<=len;i++,r=r->next){q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;} //复制串tq->next=NULL;return p;}//Sub_String4.22void LString_Concat(LString &t,LString &s,char c)//用块链存储结构,把串s插入到串t的字符c 之后{p=t.head;while(p&&!(i=Find_Char(p,c))) p=p->next; //查找字符cif(!p) //没找到{t.tail->next=s.head;t.tail=s.tail; //把s连接在t的后面}else{q=p->next;r=(Chunk*)malloc(sizeof(Chunk)); //将包含字符c的节点p分裂为两个for(j=0;j<i;j++) r->ch[j]='#'; //原结点p包含c及其以前的部分for(j=i;j<CHUNKSIZE;j++) //新结点r包含c以后的部分{r->ch[j]=p->ch[j];p->ch[j]='#'; //p的后半部分和r的前半部分的字符改为无效字符'#'}p->next=s.head;s.tail->next=r;r->next=q; //把串s插入到结点p和r之间}//elset.curlen+=s.curlen; //修改串长s.curlen=0;}//LString_Concatint Find_Char(Chunk *p,char c)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0{for(i=0;i<CHUNKSIZE&&p->ch[i]!=c;i++);if(i==CHUNKSIZE) return 0;else return i+1;}//Find_Char4.23int LString_Palindrome(LString L)//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0{InitStack(S);p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始) for(k=1;k<=S.curlen;k++){if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串else if(k>(S.curlen+1)/2){Pop(S,c); //将后半段的字符与栈中的元素相匹配if(p->ch[i]!=c) return 0; //失配}if(++i==CHUNKSIZE) //转到下一个元素,当为块中最后一个元素时,转到下一块{p=p->next;i=0;}}//forreturn 1; //成功匹配}//LString_Palindrome4.24void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t{if(t.ch) free(t.ch);t.ch=malloc((s1.length+s2.length)*sizeof(char));for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1];t.length=s1.length+s2.length;}//HString_Concat4.25int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数{for(n=0,i=0;i<=S.length-T.length;i++){for(j=i,k=0;k<T.length&&S.ch[j]==T.ch[k];j++,k++);if(k==T.length) //找到了与T匹配的子串:分三种情况处理{if(T.length==V.length)for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换S.ch[i+l-1]=V.ch[l-1];else if(T.length<V.length) //新子串长度大于原子串时:先将后部右移{for(l=S.length-1;l>=i+T.length;l--)S.ch[l+V.length-T.length]=S.ch[l];for(l=0;l<V.length;l++)S[i+l]=V[l];}else //新子串长度小于原子串时:先将后部左移{for(l=i+V.length;l<S.length+V.length-T.length;l++)S.ch[l]=S.ch[l-V.length+T.length];for(l=0;l<V.length;l++)S[i+l]=V[l];}S.length+=V.length-T.length;i+=V.length;n++;}//if}//forreturn n;}//HString_Replace4.26Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前{if(pos<1) return ERROR;if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));for(i=S.length-1;i>=pos-1;i--)S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置for(i=0;i<T.length;i++)S.ch[pos+i-1]=T.ch[pos]; //插入串TS.length+=T.length;return OK;}//HString_Insert4.27int Index_New(Stringtype s,Stringtype t)//改进的定位算法{i=1;j=1;while(i<=s[0]&&j<=t[0]){if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]])){ //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个i=i+j-2;j=1;}else{i++;j++;}}//whileif(j>t[0]) return i-t[0];}//Index_New4.28void LGet_next(LString &T)//链串上的get_next算法{p=T->succ;p->next=T;q=T;while(p->succ){if(q==T||p->data==q->data){p=p->succ;q=q->succ;p->next=q;}else q=q->next;}//while}//LGet_nextLStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针{p=pos;q=T->succ;while(p&&q){if(q==T||p->chdata==q->chdata){p=p->succ;q=q->succ;}else q=q->next;}//whileif(!q){for(i=1;i<=Strlen(T);i++)p=p->next;return p;} //发现匹配后,要往回找子串的头return NULL;}//LIndex_KMP4.30void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度{for(maxlen=0,i=1;i<S[0];i++)//串S2向右移i格{for(k=0,j=1;j<=S[0]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动{if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数else k=0; //失配时k归零if(k>maxlen) //发现了比以前发现的更长的重复子串{lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录}}//forif(maxlen){printf("Longest Repeating Substring length:%d\n",maxlen);printf("Position1:%d Position 2:%d\n",lrs1,lrs2);}else printf("No Repeating Substring found!\n");}//Get_LRepSub分析:i代表"错位值".本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen 来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).4.31void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度{if(S[0]>=T[0]){StrAssign(A,S);StrAssign(B,T);}else{StrAssign(A,T);StrAssign(B,S);} //为简化设计,令S和T中较长的那个为A,较短的那个为Bfor(maxlen=0,i=1-B[0];i<A[0];i++){if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正{jmin=1;jmax=i+B[0];}//B有一部分在A左端的左边else if(i>A[0]-B[0]){jmin=i;jmax=A[0];}//B有一部分在A右端的右边else{jmin=i;jmax=i+B[0];}//B在A左右两端之间.//以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.for(k=0,j=jmin;j<=jmax;j++){if(A[j]==B[j-i]) k++;else k=0;if(k>maxlen){lps1=j-k+1;lps2=j-i-k+1;maxlen=k;}}//for}//forif(maxlen){if(S[0]>=T[0]){lpsS=lps1;lpsT=lps2;}else{lpsS=lps2;lpsT=lps1;} //将A,B上的位置映射回S,T上的位置printf("Longest Public Substring length:%d\n",maxlen);printf("Position in S:%d Position in T:%d\n",lpsS,lpsT);}//ifelse printf("No Repeating Substring found!\n");}//Get_LPubSub分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。