#include <stdio.h>
#include <string.h>
#define MAX 100
char X[MAX],Y[MAX];
int i,j,m,n,c[MAX][MAX],b[MAX][MAX];
// function to find the length of LCS
int LCSlength()
{
m=strlen(X);
n=strlen(Y);
for (i=1;i<=m;i++) c[i][0]=0;
for (j=0;j<=n;j++) c[0][j]=0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++) {
if (X[i-1]==Y[j-1]) {
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1; /* from north west */
}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j];
b[i][j]=2; /* from north */
}
else {
c[i][j]=c[i][j-1];
b[i][j]=3; /* from west */
}
}
return c[m][n];
}
void printLCS(int i,int j)
{
if (i==0 || j==0) return;
if (b[i][j]==1) {
printLCS(i-1,j-1);
printf("%c",X[i-1]);
}
else if (b[i][j]==2)
printLCS(i-1,j);
else
printLCS(i,j-1);
}
int main()
{
while (1) {
gets(X);
if (feof(stdin)) break; /* press ctrl+z to terminate */
gets(Y);
printf("LCS length -> %d\n",LCSlength()); /* count length */
printLCS(m,n); /* reconstruct LCS */
printf("\n");
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2RlZmluZSBNQVggMTAwCmNoYXIgWFtNQVhdLFlbTUFYXTsKaW50IGksaixtLG4sY1tNQVhdW01BWF0sYltNQVhdW01BWF07CgovLyBmdW5jdGlvbiB0byBmaW5kIHRoZSBsZW5ndGggb2YgTENTCgppbnQgTENTbGVuZ3RoKCkgCgp7CiAgICAgICAgICAgbT1zdHJsZW4oWCk7CiAgICAgICAgICAgbj1zdHJsZW4oWSk7CiAgICAgICAgICAgZm9yIChpPTE7aTw9bTtpKyspIGNbaV1bMF09MDsKICAgICAgICAgICBmb3IgKGo9MDtqPD1uO2orKykgY1swXVtqXT0wOwogICAgICAgICAgIGZvciAoaT0xO2k8PW07aSsrKQogICAgICAgICAgIGZvciAoaj0xO2o8PW47aisrKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICBpZiAoWFtpLTFdPT1ZW2otMV0pIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNbaV1bal09Y1tpLTFdW2otMV0rMTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJbaV1bal09MTsgLyogZnJvbSBub3J0aCB3ZXN0ICovCiAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UgaWYgKGNbaS0xXVtqXT49Y1tpXVtqLTFdKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjW2ldW2pdPWNbaS0xXVtqXTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJbaV1bal09MjsgLyogZnJvbSBub3J0aCAqLwogICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNbaV1bal09Y1tpXVtqLTFdOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYltpXVtqXT0zOyAvKiBmcm9tIHdlc3QgKi8KICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICB9CiAgICAgICAgICByZXR1cm4gY1ttXVtuXTsKfQoKdm9pZCBwcmludExDUyhpbnQgaSxpbnQgaikgCgp7CiAgICAgICAgICAgICAgICAgIGlmIChpPT0wIHx8IGo9PTApIHJldHVybjsKICAgICAgICAgICAgICAgICAgaWYgKGJbaV1bal09PTEpIHsKICAgICAgICAgICAgICAgICAgICAgICAgIHByaW50TENTKGktMSxqLTEpOwogICAgICAgICAgICAgICAgICAgICAgICAgcHJpbnRmKCIlYyIsWFtpLTFdKTsKCiAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgIGVsc2UgaWYgKGJbaV1bal09PTIpCiAgICAgICAgICAgICAgICAgICAgICAgICBwcmludExDUyhpLTEsaik7CiAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgcHJpbnRMQ1MoaSxqLTEpOwp9CgoKaW50IG1haW4oKQoKIHsKICAgICAgICAgICAgICAgIHdoaWxlICgxKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBnZXRzKFgpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGZlb2Yoc3RkaW4pKSBicmVhazsgLyogcHJlc3MgY3RybCt6IHRvIHRlcm1pbmF0ZSAqLwogICAgICAgICAgICAgICAgICAgICAgICAgICAgZ2V0cyhZKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByaW50ZigiTENTIGxlbmd0aCAtPiAlZFxuIixMQ1NsZW5ndGgoKSk7IC8qIGNvdW50IGxlbmd0aCAqLwogICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpbnRMQ1MobSxuKTsgLyogcmVjb25zdHJ1Y3QgTENTICovCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBwcmludGYoIlxuIik7CiAgICAgICAgICAgICAgIH0KfQ==