学步园

//LCS DP 滚动数组优化
#include<cstdio>
#include<cstring>
using namespace std;
int n,la,lb,lcs[2][5005],creat[5005]={0};
char stra[5005],strb[5005];
int main(){
int ic=0;//count in the array creat[]
//input
    scanf("%s%s",stra,strb);
    la=strlen(stra);
    lb=strlen(strb);
for(int i=0;i<=(la>lb?la:lb);i++)
        lcs[0][i]=lcs[1][i]=0;
//recurrence
    for(int i=1;i<=la;i++)
for(int j=1;j<=lb;j++){
if(stra[i-1]==strb[j-1]){
                 lcs[i%2][j]=lcs[(i-1)%2][j-1]+1;
                 creat[ic]=i-1;
                 ic++;
            }
else{
if(lcs[i%2][j-1]>lcs[(i-1)%2][j])   lcs[i%2][j]=lcs[i%2][j-1];
else                                lcs[i%2][j]=lcs[(i-1)%2][j];
            }
        }
    printf("%d\n",lcs[la%2][lb]);
//printf the LCS
    for(int i=0;i<lcs[la%2][lb];i++)
        printf("%c",stra[creat[i]]);
    printf("\n");
return 0;
}