| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 35595 | Accepted: 14185 |
Description
Input
Output
Sample Input
abcfbc abfcab programming contest abcd mnp
Sample Output
4 2 0
-----------------------------------------------------------------------------
状态转移方程：
if(st1[i]==st2[j])
res[i+1][j+1]=res[i][j]+1;
else
res[i+1][j+1]= res[i][j+1]>res[i+1][j] ?res[i][j+1]:res[i+1][j] ;
res[i][j]表示字符串字串st1[0-i],st2[0-j]的公共子序列长度。
#include<stdio.h>
#include<stdlib.h> //最长公共子序列，别的不说了
#include<string.h>
#define MAX 1001 //唯一注意的是数组的大小
#define Max(x,y) (x)>(y)?(x):(y)
int main()
{
char string1[MAX];
char string2[MAX];
//char string1a[26];
//char string1b[26];
int string[MAX][MAX];
int max1,max2,i,j;
while(scanf("%s%s",string1,string2)!=EOF)
{
memset(string, 0, sizeof(string));
//gets(string1);
//gets(string2);
//memset(c,0,sizeof(string));
max1=strlen(string1);
max2=strlen(string2);
for(i=1;i<=max1;i++)
for(j=1;j<=max2;j++)
{
if(string1[i-1]==string2[j-1])
{
string[i][j]=string[i-1][j-1]+1;//关键1
}
else
string[i][j] = Max(string[i][j-1], string[i-1][j]);//关键2
}
printf("%d\n",string[max1][max2]);
}
return 0;
}
POJ 1458 Common Subsequence,布布扣,bubuko.com
原文：http://blog.csdn.net/zzucsliang/article/details/21388517