厳蔚敏データ構造4.30一番長い共通文字列

元の列はSで、最初の文字列はS 1で、最初から、もう一つの文字列S 2とS 1は右に1位、2位、3位をずらす…S 1と一致して、共通の文字列を探して、maxlenで見つけた最大の長さを記録します.これを知ると簡単です.この問題も難しくないです.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define ok 1
#define error 0
#define true 1
#define false 0
#define overflow -1
using namespace std;
typedef int status;
#define maxsize 255
typedef char sstring[maxsize+1];
status strassign(sstring &s,char *ch)
{
    int i=0;
    char *p=ch;
    while(i<maxsize&&*p)s[++i]=*p++;
    s[0]=i;
    if(*p)return error;
    else return ok;
}
void strcpy(sstring &t,sstring s)
{
    int i;
    for(i=0; i<=s[0]; i++)
        t[i]=s[i];
}
int strcompare(sstring s,sstring t)
{
    int i=1;
    while(i<=s[0]&&i<=t[0]&&s[i]==t[i])i++;
    if(i<=s[0])
        if(i<=t[0])return s[i]-t[i];
        else return  s[i];
    else if(i<=t[0])return -t[i];
    else return  0;
}
status concat(sstring &t,sstring s1,sstring s2)
{
    int i,j;
    for(i=1; i<=s1[0]; i++)t[i]=s1[i];
    if(s1[0]+s2[0]<=maxsize)
    {
        for(j=1; j<=s2[0]; j++)t[i++]=s2[j];
        t[0]=s1[0]+s2[0];
        return ok;
    }
    else
    {
        for(j=1; j<=maxsize-s1[0]; j++)t[i++]=s2[j];
        t[0]=maxsize;
        return error;
    }
}
status substring(sstring &sub,sstring s,int pos, int len) {
    int i;
    if(pos<1||pos>s[0]||len<0||len>s[0]-pos+1)
        return error;
    for(i=1; i<=len; i++)sub[i]=s[pos+i-1];
    sub[0]=len;
    return ok;
}
void putdata(sstring s)
{
    int i;
    printf("
");
    for(i=1; i<=s[0]; i++)
        printf("%c",s[i]);
}

/*4.30*/
void get_maxsub(sstring s)
{
    int maxlen=0,i,j,k,l;
    int pos1,pos2;
    for(i=1;i<=s[0];i++)  /*S1    i */
    {
        for(k=0,j=1;j<=s[0]-i;j++) /*j  S1  ，j+i  S2  ，j+i     S     ， s[0]*/
        {
            if(s[j]==s[j+i])
                k++;
            else
                k=0;
            if(k>maxlen)
            {
                pos1=j-k+1;   /*   j ， S1                +1*/
                pos2=pos1+i;
                maxlen=k;

            }
        }
    }
    if(maxlen>0)
    {
        printf("        ：
");
        l=pos1;
        for(i=1;i<=maxlen;i++)
        {
            printf("%c",s[l++]);
        }
        printf("
   ：%d",maxlen);
        printf("
         ：%d,          ：%d",pos1,pos2);
    }
    else
        printf("      ！
");
}

int main()
{
    sstring a;
    strassign(a,"abcdabcdabcd");
    printf("   :");
    putdata(a);
    printf("
");
    get_maxsub(a);
    return 0;
}