算法与数据结构考研试题精析(第二版)第4章串答案

for（j=０；j

［算法讨论］假定字符串中的数均不超过32767，否则，需用长整型数组及变量。 3、[题目分析]设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。

int LongestString(char s[],int n)

//串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。

{int index=0,max=0; //index记最长的串在s串中的开始位置，max记其长度 int length=1,i=0,start=0; //length记局部重复子串长度，i为字符数组下标 while(i

if(s[i]==s[i+1]) {i++; length++;} else //上一个重复子串结束

{if(max

i++;start=i;length=1; //初始化下一重复子串的起始位置和长度

}

printf(“最长重复子串的长度为%d，在串中的位置%d\\n”，max,index); return(max); }//算法结束

[算法讨论]算法中用i

算法的时间复杂度为O(n），每个字符与其后继比较一次。

4、[题目分析]教材中介绍的串置换有两种形式：第一种形式是replace（s,i,j,t），含义是将s串中从第i个字符开始的j个字符用t串替换,第二种形式是replace(s,t,v)，含义是将s串中所有非重叠的t串用v代替。我们先讨论第一种形式的替换。因为已经给定顺序存储结构，我们可将s串从第（i+j-1）到串尾（即s.curlen）移动t.curlen-j绝对值个位置（以便将t串插入）：若j>t.curlen，则向左移；若j

int replace(strtp s,t,int i,j)

//s和t是用一维数组存储的串，本算法将s串从第i个字符开始的连续j个字符用t串置换，操作成功返回1，否则返回0表示失败。 {if(i<1 || j<0 || t.curlen+s.curlen-j>maxlen)

{printf(“参数错误\\n”);exit(0);} //检查参数及置换后的长度的合法性。 if(j=i+j-1;k--) s.ch[k+t.curlen-j]=s.ch[k]; else if (j>t.curlen) //s串中被替换子串的长度小于t串的长度。 for(k=i-1+j;k<=s.curlen-1;k++) s.ch[k-(j-t.curlen)]=s.ch[k];

for(k=0;k