这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
//ID:百练oj2806 最长公公子序列 //网站:C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛 //地址:http://www.cppleyuan.com/ //个人主页:www.wutianqi.com
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAX_LEN 1000
char sz1[MAX_LEN];
char sz2[MAX_LEN];
int aMaxLen[MAX_LEN][MAX_LEN];
int main()
{
while(scanf("%s%s", sz1+1, sz2+1) == 2)
{
int nLength1 = strlen(sz1+1); //
int nLength2 = strlen(sz2+1); //
int i, j;
for(i = 0; i <= nLength1; i++)
aMaxLen[i][0] = 0;
for(j = 0; j <= nLength2; j++)
aMaxLen[0][j] = 0;
for(i = 1; i <= nLength1; i++)
for(j = 1; j <= nLength2; j++)
if(sz1[i] == sz2[j])
aMaxLen[i][j] = aMaxLen[i-1][j-1] + 1;
else
{
int nLen1 = aMaxLen[i-1][j];
int nLen2 = aMaxLen[i][j-1];
if(nLen1 > nLen2)
aMaxLen[i][j] = nLen1;
else
aMaxLen[i][j] = nLen2;
}
printf("%d\n", aMaxLen[nLength1][nLength2]);
}
return 0;
}