代码如下:
#include<iostream>
#include<sstream>
using namespace std;
int v[1000][1000];
short dir[1000][1000];
char A[1000],B[1000];
int r,c;
int LCS()
{
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
if(A[i-1]==B[j-1])
{
v[i][j]= v[i-1][j-1]+1;
dir[i][j]=1;
}
else if(v[i-1][j]>=v[i][j-1])
{
v[i][j]=v[i-1][j];
dir[i][j]=0;
}
else
{
v[i][j]=v[i][j-1];
dir[i][j]=2;
}
}
return v[r][c];
}
void print(int ri,int ci)
{
if(ri==0||ci==0)
return;
if(dir[ri][ci]==1)
{
print(ri-1,ci-1);
printf("%c ",A[ri-1]);
}
else if(dir[ri][ci]==0)
print(ri-1,ci);
else
print(ri,ci-1);
}
int main()
{
scanf("%s%s",A,B);
r=strlen(A),c=strlen(B);
printf("%d\n",LCS());
print(r,c);
printf("\n");
return 0;
}
分享到:
相关推荐
清华大学ACM模板,汇集了很多算法的标准模式,而且有详细的算法讲解,图论、数论、网络流等等,从浅到深,彻底解剖,是ACM进阶者不二的选择~!
矩阵快速幂的模板,需要自己根据实际题目更改矩阵大小和数据类型,以免WA和TLE。经过矩阵乘法上的稀疏矩阵优化和int64的乘法取模幂优化,效率应该比较高。视情况使用mult()函数或直接使用乘法。代码中每个函数有注释...
模板ACM———浙江大学与吉林大学 模板ACM———浙江大学与吉林大学 模板ACM———浙江大学与吉林大学 模板ACM———浙江大学与吉林大学 模板ACM———浙江大学与吉林大学
ACM培训——算法入门---------------------------------算法入门ACM培训——算法入门---------------------------------算法入门ACM培训——算法入门---------------------------------算法入门
ACM数论——ppt(天津大学)ACM数论——ppt(天津大学)
ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板AACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM ...
ACM准备模板 堆排序模板 acm 堆 排序
上海交大ACM模板 考研复试机试参考资料
一 个报告,新手用 没什么用的 随便看看个报告,新手用 没什么用的 随便看看个报告,新手用 没什么用的 随便看看
大学生acm竞赛——10年12月竞赛题库 希望对你们有所帮助
acm模板acm模板acm模板acm模板acm模板acm模板acm模板acm模板
给刚接触 ACM 的同学提供做题时输入输出的知识。
kuangbin的ACM模板kuangbin的ACM模板kuangbin的ACM模板kuangbin的ACM模板kuangbin的ACM模板kuangbin的ACM模板
浙江大学ACM模板
浙江大学acm,吉林大学acm模板浙江大学acm,吉林大学acm模板浙江大学acm,吉林大学acm模板浙江大学acm,吉林大学acm模板浙江大学acm,吉林大学acm模板浙江大学acm,吉林大学acm模板浙江大学acm,吉林大学acm模板浙江...
给刚接触ACM的同学提供字符串处理和有关随机数生成知识。
完整版kuangbin的ACM模板(全新).pdf 从最简单的搜索到几何问题等模板 涵盖了所有ACM专题的内容
acm算法模板,包含竞赛需要的各类算法。。。。。。
浙江大学的acm模板,比较全面也比较权威,质量很好,总结了很多算法的模板
ACM模板和一些题目的代码实现 ACM模板和一些题目的代码实现 ACM模板和一些题目的代码实现 ACM模板和一些题目的代码实现 ACM模板和一些题目的代码实现 ACM模板和一些题目的代码实现 ACM模板和一些题目的代码实现 ACM...