NYOJ 36 LCS(最长公共子序列)
2024-08-27 17:55:52
题目链接:
http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=36
最长公共子序列
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
- 咱们就不拐弯抹角了,如题,需要你做的就是写一个程序,得出最长公共子序列。
tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
- 输入
- 第一行给出一个整数N(0<N<100)表示待测数据组数
接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000. - 输出
- 每组测试数据输出一个整数,表示最长公共子序列长度。每组结果占一行。
- 样例输入
-
2
asdf
adfsd
123abc
abc123abc - 样例输出
-
3
6#include<bits/stdc++.h>
using namespace std;
int f_max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int t;
scanf("%d",&t);
getchar();
while(t--)
{
char a[];
char b[];
gets(a);
gets(b);
int l1=strlen(a);
int l2=strlen(b);
int dp[l1+][l2+];
memset(dp,,sizeof(dp));
//dp[i][j]表示a0.....ai和b0....bj的LCS长度
for(int i=; i<=l1; i++)
{
for(int j=; j<=l2; j++)
{
if(a[i-]==b[j-])//以为i,j是从1开始的,所以i-1,j-1
{
dp[i][j]=dp[i-][j-]+;
}
else
{
dp[i][j]=f_max(dp[i-][j],dp[i][j-]);
}
}
}
printf("%d\n",dp[l1][l2]);
}
return ;
}
最新文章
- 让我们一起写出更有效的CSharp代码吧,少年们!
- ios import和@class的区别
- oracle查找重复记录
- ubuntu 下安装软件,卸载,查看已经安装的软件
- crm工作机会实体
- redhat初始化yum源,使用阿里云yum源
- 51Nod--1011最大公约数GCD
- 关于html+ashx开发中几个问题的解决方法的感想和总结
- 面试心得随谈&;线程并发的总结
- Linux(CentOS7)yum安装卸载命令,离线下载安装包
- 【转】forbids in-class initialization of non-const static member不能在类内初始化非const static成员
- (转)解决 TortoiseGit 诡异的 Bad file number 问题
- eclipse设置是否自动跳转切换到debug视图模式
- MySql cmd下的学习笔记 —— 有关常用函数的介绍(数学函数,聚合函数等等)
- Knn:Knn实现对150朵共三种花的实例的萼片长度、宽,花瓣长、宽数据统计,根据一朵新花的四个特征来预测其种类
- 怎样让两个DIV在同一水平线上面显示
- 获取relatedTarget属性
- 织梦会员 Warning: preg_replace(): The /e modifier is no longer supported, us...
- centos7切换gnome3桌面与gnome经典桌面
- python生成指定文件夹目录树
热门文章
- [AMPPZ2014]Petrol
- Myeclipse打war包方法
- druapl7:";Notice: A non well formed numeric value encountered 在 _hierarchical_select_hierarchy_generate() ";
- JQuery和原生JavaScript实现网页定位导航特效
- css盒模型(Box Model)
- 浏览器根对象document之数值和布尔属性
- 一步一步pwn路由器之radare2使用实战
- canvas验证码 - 随机字母数字
- Material适配2 - 高级篇
- maven 安装与配置最佳实践