百练oj2806 最长公公子序列

//ID:百练oj2806 最长公公子序列
//Name:Tanky_Woo
//网站:C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛
//地址:http://www.cppleyuan.com/
//个人主页:www.wutianqi.com
//豆瓣小组:http://www.douban.com/group/cppleyuan/
//QQ:493841534/17611904
//QQ群:C++奋斗乐园①群:19333724(满) ②群:23840480 ③群:17314377 ④群:23829384
//转载请写上本帖链接和“C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛”

#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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注