Longest Common Subsequence
Problem
Given a sequence A = < a1, a2, ..., am >, let sequence B = < b1, b2, ..., bk > be a subsequence of A if there exists a strictly increasing sequence ( i1<i2<i3 ..., ik ) of indices of A such that for all j = 1,2,...,k, aij = bj. For example, B = < a, b, c, d > is a subsequence of A= < a, b, c, f, d, c > with index sequence < 1, 2, 3 ,5 >.
Given two sequences X and Y, you need to find the length of the longest common subsequence of X and Y.
Input
The input may contain several test cases.
The first line of each test case contains two integers N (the length of X) and M(the length of Y), The second line contains the sequence X, the third line contains the sequence Y, X and Y will be composed only from lowercase letters. (1<=N, M<=100)
Input is terminated by EOF.
Output
Output the length of the longest common subsequence of X and Y on a single line for each test case.
Sample input
6 4
abcfdc
abcd
2 2
ab
cd
Sample output
4
0
#include <stdio.h>
char x[105],y[105];
int c[109][109],i,j,leny,lenx;
int main()
{
while(scanf("%d %d",&lenx,&leny)!=EOF){
scanf("%s",&x);
scanf("%s",&y);
for(i=0;i<=leny;i++)
c[0][i]=0;
for(i=1;i<=lenx;i++)
c[i][0]=0;
for(i=1;i<=lenx;i++){
for(j=1;j<=leny;j++){
if(x[i-1]==y[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];
}
}
}
printf("%d\n",c[lenx][leny]);
}
return 0;
}