paste bin

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;

int LCS(char* s1, char* s2,char *res)
{
    int i,j,M,N,k=0,upbd;
    M=strlen(s1);
    N=strlen(s2);
    int **dp;
    dp=new int* [M+2];
    for(i=0;i<M+2;i++)
        dp[i]=new int [N+2];
    for(i=0;i<N+2;i++)
        dp[0][i]=0;
    
    for(i=1;i<M+1;i++)
    {
        dp[i][0]=0;
        for(j=1;j<N+1;j++)
        {
            if(s1[i-1]==s2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    k=dp[M][N];

    i=M;
    j=N;
    upbd=k;
    res[k]='\0';
    while(i>0 && j>0)
    {
        if(dp[i-1][j]==dp[i-1][j-1] && dp[i-1][j-1]==dp[i][j-1] )
        {
            if (dp[i][j]==dp[i-1][j-1]+1)
                res[--upbd]=s1[i-1];
            i--;
            j--;
        }
        else
        {
            if(dp[i-1][j]==dp[i][j])
                i--;
            else
                j--;
        }
    }
    for(i=0;i<M+2;i++)
        delete [] dp[i];
    delete [] dp;

    return k;
}

void solve(char *s)
{
    char *s1,*s2,*res,*target;
    int N=strlen(s),i,d,maxVal=-1;
    s1=new char [N+1];
    s2=new char [N+1];
    res=new char [N+1];
    target=new char [N+1];
    for(i=1;i<N;i++)
    {
        strcpy(s1,s);
        s1[i]=0;
        strcpy(s2,s+i);

        d=LCS(s1,s2,res);
        if(d>maxVal)
        {
            maxVal=d;
            strcpy(target,res);
        }
    }
    printf("%s\n",target);
    delete [] s1;
    delete [] s2;
    delete [] res;
    delete [] target;
}

#define MAXLENGTH 303
int main(void)
{
    char s[MAXLENGTH];
    while(scanf("%s",s)!=EOF)
    {
        if(strcmp("#END",s)==0)
            break;
        solve(s);

    }

    return 0;
}