[題目分析]設以字符數組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）每個字符與其後繼比較一次
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22613.html
