数据结构考研分类复习真题 第四章 答案[14]

[题目分析]设以字符数组s表示串重复子串的含义是由一个或多个连续相等的字符组成的子串其长度用max表示初始长度为将每个局部重复子串的长度与max相比若比max大则需要更新max并用index记住其开始位置

int LongestString(char s[]int n)//串用一维数组s存储长度为n本算法求最长重复子串返回其长度

{int index=max=;//index记最长的串在s串中的开始位置max记其长度

int length=i=start=;//length记局部重复子串长度i为字符数组下标

while(i<n)

if(s[i]==s[i+]) {i++; length++;}

else //上一个重复子串结束

{if(max<length) {max=length; index=start; } //当前重复子串长度大则更新max

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

}

printf(最长重复子串的长度为%d在串中的位置%d\nmaxindex);

return(max);

}//算法结束

[算法讨论]算法中用i<n来控制循环次数因C数组下标从 开始故长度为n的串其最后一个字符下标是n当i最大为n时条件语句中s[i+]正好是s[n]即最后一个字符子串长度的初值数为表示一个字符自然等于其身

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

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []