i//for if( maxlen) printf("Longest Repeating Substring length: %d \n", maxlen); printf("Position1: %d Position 2: %d\n", Irs1, Irs2) else printf("No Repeating Substring found! n"); ∥ Get LRepsub 分析i代表"错位值"本算法的思想是,依次把串S的一个副本S2向右错位平移1 格,2格,3格,与自身SI相匹配,如果存在最长重复子串,则必然能在此过程中被发 现用变量lrsl,lrs2, maxlen来记录已发现的最长重复子串第一次出现位置,第二次 出现位置和长度题目中未说明"重复子串"是否允许有重叠部分本算法假定允许. 如不允许,只需在第二个for语句的循环条件中加上k<即可本算法时间复杂度 为 O(Strlen(Sy2) 4.31 void get LPubSub( Stringtype S, Stringtype T∥求串S和串T的最长公共子串位置 和长度 if(SOP=TOD StrAssign(A, S), StrAssign(B, T) StrAssign(A, T), StrAssign(B, S); }∥为简化设计令S和T中较长的那个为A,较短的那个为B for(maxlen=0, F1-B[O]: I<AO; 1++) if(i0)为B相对于A的错位值向左为负,左端对齐为0,向右为正 jmin=l; jmax=i+BO B有一部分在A左端的左边 else if( A[O]-BIOD jmin= Imax=A[O小 }/B有一部分在A右端的右边 else jmin=i,imax=i+BIO }/B在A左右两端之间 ∥以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合 的区间)的端点 dmin, max for(k=0,F jmin j<=jmax:j++)}//for if(maxlen) { printf("Longest Repeating Substring length:%d\n",maxlen); printf("Position1:%d Position 2:%d\n",lrs1,lrs2); } else printf("No Repeating Substring found!\n"); }//Get_LRepSub 分析:i 代表"错位值".本算法的思想是,依次把串 S 的一个副本 S2 向右错位平移 1 格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发 现.用变量 lrs1,lrs2,maxlen 来记录已发现的最长重复子串第一次出现位置,第二次 出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许. 如不允许,只需在第二个 for 语句的循环条件中加上 k<=i 即可.本算法时间复杂度 为 O(Strlen(S)^2). 4.31 void Get_LPubSub(Stringtype S,Stringtype T)//求串 S 和串 T 的最长公共子串位置 和长度 { if(S[0]>=T[0]) { StrAssign(A,S);StrAssign(B,T); } else { StrAssign(A,T);StrAssign(B,S); } //为简化设计,令 S 和 T 中较长的那个为 A,较短的那个为 B for(maxlen=0,i=1-B[0];i<A[0];i++) { if(i<0) //i 为 B 相对于 A 的错位值,向左为负,左端对齐为 0,向右为正 { jmin=1;jmax=i+B[0]; }//B 有一部分在 A 左端的左边 else if(i>A[0]-B[0]) { jmin=i;jmax=A[0]; }//B 有一部分在 A 右端的右边 else { jmin=i;jmax=i+B[0]; }//B 在 A 左右两端之间. //以上是根据 A 和 B 不同的相对位置确定 A 上需要匹配的区间(与 B 重合 的区间)的端点:jmin,jmax. for(k=0,j=jmin;j<=jmax;j++)