?? 4.30.c
字號:
4.30⑤ 假設以定長順序存儲結構表示串,試設計
一個算法,求串s中出現的第一個最長重復子串及
其位置,并分析你的算法的時間復雜度。
要求實現以下函數:
void CommonStr(SString s, SString &sub, int &loc);
/* 求串s中出現的第一個最長重復子串sub及其位置loc */
定長順序串SString的類型定義:
typedef unsigned char SString[MAXSTRLEN+1];
/* s[0] is the string's length */
void CommonStr(SString s, SString &sub, int &loc)
/* 求串s中出現的第一個最長重復子串sub及其位置loc */
{
int maxlength=0,i,j,count,k;
for(i=1;i<s[0]+1-maxlength;i++) //順序鎖定一個字符,掃描其前面與之同字符則繼續比較對應下一個字符
{
for(count=0,j=1,k=0;j<i&&i+k<=s[0];k++)
{
if(s[j+k]==s[i+k])
{
count++;
if(count>maxlength){loc=j;maxlength=count;}
}//if
else {count=0;j++;k=0;k--;} //k--消除外層循環的k++
}//for
}//for
sub[0]=maxlength;
for(i=1;i<=maxlength;i++,j++) sub[i]=s[loc-1+i];
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -