/*the longest comman sequence
*input :two string s, t, length are n,m respectively
0 if i = 0 or j = 0
*c[i][j] = { c[i-1][j-1] + 1 if s[i] = t[j]
max(c[i][j-1],c[i-1][j]) if s[i] != t[j]
*output: return c[n][m]
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
char str1[MAX], str2[MAX];
char B[MAX][MAX];
int l1[MAX],l2[MAX];
int LCS(char *s,char *t)
{
int i, j, k;
int ls = strlen(s+1),lt = strlen(t+1);
//printf("%d %d\n",strlen(s),strlen(t));
//printf("%d %d",ls,lt);
for(i=0; i<=lt; i++)
l1[i] = 0;
for(i=1; i<=ls; i++)
{
for(j=1; j<=lt; j++)
{
if(s[i] == t[j])
{
l2[j] = l1[j-1] + 1;
B[i][j] = '1';
}
else
{
if(l2[j-1]>l1[j])
{
l2[j] = l2[j-1];
B[i][j] = '2';
}
else
{
l2[j] = l1[j];
B[i][j] = '3';
}
}
}
for(k=0; k<=lt; k++)
{
l1[k] = l2[k];
}
}
return l2[lt];
}
void Construct(char *s,char b[][MAX], int n, int m)
{
if(n==0||m==0)
{
return ;
}
else
{
if(b[n][m] == '1')
{
Construct(s,b,n-1,m-1);
printf("%c",s[n]);
}
else if(b[n][m] =='2')
{
Construct(s,b,n,m-1);
}
else
{
Construct(s,b,n-1,m);
}
}
}
int main()
{
printf("请输入第一个字符串 :\n");
scanf("%s",str1+1);
printf("请输入第二个字符串 :\n");
scanf("%s",str2+1);
printf("最长公共子序列的长度 :%d\n",LCS(str1, str2));
printf("最长公共子序列 :");
Construct(str1,B,strlen(str1+1),strlen(str2+1));
while(1);
return 0;
}
