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];
}