#include <stdio.h>
#include <string.h>
#define N 100
int lcslength(char a[], char b[], int c[N][N]);
char *lcs(char str[], char a[], char b[]);
int c[N][N];
char str[N];
int lcslength(char a[], char b[], int c[N][N])
{
int i, j, sa , sb;
sa = strlen(a);
sb = strlen(b);
for (i = 0; i < sa; i++)
c[i][0] = 0;
for (j = 0; j < sb; j++)
c[0][j] = 0;
for(i = 1; i < sa; i++ )
for( j = 1; j < sb; j++)
{
if(a[i-1] == b[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
}
if(c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
}
else
{
c[i][j] = c[i][j-1];
}
}
return c[sa][sb];
}

char *lcs(char str[], char a[], char b[])
{
int i, j;
int k;
i = strlen(a);
j = strlen(b);
k = lcslength(a,b,c);
str[k] = '\0';
while(k >= 0)
{
if(c[i][j] == c[i-1][j]) i--;
if(c[i][j] == c[i][j-1]) j--;
else
{
str[--k] = a[i-1];
i--;
j--;
}
}
return str; //str 怎么没有值啊!总是指向空串?
}

int main()
{
char a[N], b[N];
printf("input the first array:\n");
gets(a);
printf("input the second array:\n");
gets(b);
printf("the lcs:\n");
puts(lcs(str, a, b));
return 0;
}