SubsirComunMaximal

#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMax 1001
#define maxim(a,b)((a>b)?a:b)
using namespace std;
int M,N;
char A[NMax],B[NMax];
int D[NMax][NMax];

int main(void)
{
    int i,j;
    freopen("subsircomunmaximal.in","r",stdin);
    freopen("subsircomunmaximal.out","w",stdout);
    scanf("%s %s",A,B);
    M=strlen(A);
    N=strlen(B);
    for(i=1;i<=M;++i)
        for(j=1;j<=N;++j)
            if(A[i-1]==B[j-1])
                D[i][j]=1+D[i-1][j-1];
            else
                D[i][j]=maxim(D[i-1][j],D[i][j-1]);
    int L=0;
    char sir[1000];
    for(i=M,j=N;i;)
        if(A[i-1]==B[j-1])
            sir[L++]=A[i-1],--i,--j;
        else
            if(D[i-1][j]<D[i][j-1])
            --j;
        else
            --i;
    sir[L]='\0';
    reverse(sir,sir+L);
    printf("%s\n",sir);
    return 0;
}