很简单的一道题
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char x[10005],y[10005];
int c[1005][1005];
int Lcs_length( char *str1, char *str2)
{
int len1 = strlen(str1),
len2 = strlen(str2);
int i,j;
for( i = 1; i <= len1; i++)
c[i][0] = 0;
for ( j = 0; j <= len2; j++)
c[0][j] = 0;
for( i = 1; i <= len1; i++)
for( j = 1; j <= len2; j++) {
if( str1[i-1] == str2[j-1] )
c[i][j] = c[i-1][j-1] + 1;
else 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[len1][len2];
}
void Find_Lcs( char *str1, char *str2)
{
int i,j,length;
int len1 = strlen(str1),
len2 = strlen(str2);
length = Lcs_length(str1, str2);
printf("%d\n", length);
}
int main()
{
while(scanf("%s%s",x,y) != EOF){
Find_Lcs(x,y);
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(c,0,sizeof(c));
}
return 0;
}
