正文
UVa 10405 & POJ 1458 Longest Common Subsequence
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
求最长公共子序列LCS，用动态规划求解。
UVa的字符串可能含有空格，开始用scanf("%s", s);就WA了一次...那就用gets吧，怪不得要一行放一个字符串呢。
（本来想用fgets的，可是又放弃了，形式麻烦、代码长是一小方面，另一方面fgets把'\n'字符也读入，还要做额外的处理...虽然gets有传说中的缓冲区溢出漏洞，不过多加注意一下就好啦，个人认为代码还没大到要用那些工程性的东西的时候）
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1000+10
using namespace std; char s1[MAXN], s2[MAXN];
int c[MAXN][MAXN]; int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
while (gets(s1) && gets(s2))
{
int m = strlen(s1);
int n = strlen(s2);
memset(c, , sizeof(c));
for (int i = ; i <= m; i++)
for (int j = ; j <= n; j++)
{
if (s1[i-] == s2[j-]) c[i][j] = c[i-][j-] + ;
else c[i][j] = max(c[i][j-], c[i-][j]);
}
printf("%d\n", c[m][n]);
}
return ;
}
在POJ中字符串用空格分割，字符串中不含空格，并且两个字符串在同一行上，用scanf("%s", s)替换get(s)就可以了
下面是打印LCS的代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1000+10
using namespace std; char s1[MAXN], s2[MAXN];
int c[MAXN][MAXN]; void print_LCS(int i, int j)
{
if (i == || j == ) return;
if (s1[i-] == s2[j-])
{
print_LCS(i-, j-);
printf("%c", s1[i-]);
}
else if (c[i-][j] == c[i][j]) print_LCS(i-, j);
else if (c[i][j-] == c[i][j]) print_LCS(i, j-);
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
while (scanf("%s%s", s1, s2) != EOF)
{
int m = strlen(s1);
int n = strlen(s2);
memset(c, , sizeof(c));
for (int i = ; i <= m; i++)
for (int j = ; j <= n; j++)
{
if (s1[i-] == s2[j-]) c[i][j] = c[i-][j-] + ;
else c[i][j] = max(c[i][j-], c[i-][j]);
}
printf("%d\n", c[m][n]);
// print the LCS
print_LCS(m, n);
printf("\n");
}
return ;
}
2
UVa 10405 & POJ 1458 Longest Common Subsequence的更多相关文章- 【POJ - 1458】Common Subsequence（动态规划）
Common Subsequence Descriptions: A subsequence of a given sequence is the given sequence with some e ...
- POJ 1458：Common Subsequence
Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 41957 Accepted: 16 ...
- UVA 10405 Longest Common Subsequence (dp + LCS)
Problem C: Longest Common Subsequence Sequence 1: Sequence 2: Given two sequences of characters, pri ...
- [Algorithms] Longest Common Subsequence
The Longest Common Subsequence (LCS) problem is as follows: Given two sequences s and t, find the le ...
- 动态规划求最长公共子序列（Longest Common Subsequence, LCS）
1. 问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与 ...
- LintCode Longest Common Subsequence
原题链接在这里:http://www.lintcode.com/en/problem/longest-common-subsequence/ 题目: Given two strings, find t ...
- [UCSD白板题] Longest Common Subsequence of Three Sequences
Problem Introduction In this problem, your goal is to compute the length of a longest common subsequ ...
- LCS（Longest Common Subsequence 最长公共子序列）
最长公共子序列 英文缩写为LCS(Longest Common Subsequence).其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已 ...
- Longest Common Subsequence
Given two strings, find the longest common subsequence (LCS). Your code should return the length of ...
随机推荐- 打造android偷懒神器———RecyclerView的万能适配器
转载请注明出处谢谢:http://www.cnblogs.com/liushilin/p/5720926.html 很不好意思让大家久等了,本来昨天就应该写这个的,无奈公司昨天任务比较紧,所以没能按时 ...
- EMS电子面单接口对接使用-免费版
快递鸟电子面单接口,可一次对接15家快递公司, 无需和每一家快递公司做对接.支持快递有四通一达.顺丰.EMS.宅急送.德邦.优速等15家快递公司,对顺丰有电子面单服务需求的可以选择顺丰自有的电子面单或 ...
- 【转】tomcat下jndi的三种配置方式
jndi(Java Naming and Directory Interface,Java命名和目录接口)是一组在Java应用中访问命名和目录服务的API.命名服务将名称和对象联系起来,使得我们可以用 ...
- MFC窗口重绘
Invalidate()与 UpdateAllViews()有什么分别 Invalidate()是让程序重画窗口. UpdateAllViews()是在DOC/VIEW结构中, 当一个视图的数据改变后 ...
- js如何打印object对象
js调试中经常会碰到输出的内容是对象而无法打印的时候,光靠alert只能打印出object标示,却不能打印出来里面的内容,甚是不方便,于是各方面整理总结了如下一个函数,能够将数组或者对象这类的结果一一 ...
- js关于闭包的内存的问题--deep down
js有一个东西叫做GC(garbage collection )垃圾回收机制;js中有两种类型:js基本数据类型,js引用类型; 当一个函数[对象]--引用类型被引用后,过后,出了它的功能之后,gc会 ...
- Itext简绍及操作PDF文件
iText简介 iText是著名的开放源码的站点sourceforge一个项目,是用于生成PDF文档的一个java类库.通过iText不仅可以生成PDF或rtf的文档,而且可以将XML.Html文件转 ...
- 【HNOI 2017】大佬
Problem Description 人们总是难免会碰到大佬.他们趾高气昂地谈论凡人不能理解的算法和数据结构,走到任何一个地方,大佬的气场就能让周围的人吓得瑟瑟发抖,不敢言语.你作为一个 OIer, ...
- EasyMall注册功能
EasyMall注册功能 1. 环境搭建 创建一个EasyMall的web应用 配置www.easymall.com网站,并配置为缺省的虚拟主机,将EasyMall配 置为缺省的web应用,在配置in ...
- vue 双向数据绑定 Vue事件介绍 以及Vue中的ref获取dom节点
<template> <div id="app"> <h2>{{msg}}</h2> <input type="te ...
Common Subsequence Descriptions: A subsequence of a given sequence is the given sequence with some e ...
Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 41957 Accepted: 16 ...
Problem C: Longest Common Subsequence Sequence 1: Sequence 2: Given two sequences of characters, pri ...
The Longest Common Subsequence (LCS) problem is as follows: Given two sequences s and t, find the le ...
1. 问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与 ...
原题链接在这里:http://www.lintcode.com/en/problem/longest-common-subsequence/ 题目: Given two strings, find t ...
Problem Introduction In this problem, your goal is to compute the length of a longest common subsequ ...
最长公共子序列 英文缩写为LCS(Longest Common Subsequence).其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已 ...
Given two strings, find the longest common subsequence (LCS). Your code should return the length of ...
- 打造android偷懒神器———RecyclerView的万能适配器
转载请注明出处谢谢:http://www.cnblogs.com/liushilin/p/5720926.html 很不好意思让大家久等了,本来昨天就应该写这个的,无奈公司昨天任务比较紧,所以没能按时 ...
- EMS电子面单接口对接使用-免费版
快递鸟电子面单接口,可一次对接15家快递公司, 无需和每一家快递公司做对接.支持快递有四通一达.顺丰.EMS.宅急送.德邦.优速等15家快递公司,对顺丰有电子面单服务需求的可以选择顺丰自有的电子面单或 ...
- 【转】tomcat下jndi的三种配置方式
jndi(Java Naming and Directory Interface,Java命名和目录接口)是一组在Java应用中访问命名和目录服务的API.命名服务将名称和对象联系起来,使得我们可以用 ...
- MFC窗口重绘
Invalidate()与 UpdateAllViews()有什么分别 Invalidate()是让程序重画窗口. UpdateAllViews()是在DOC/VIEW结构中, 当一个视图的数据改变后 ...
- js如何打印object对象
js调试中经常会碰到输出的内容是对象而无法打印的时候,光靠alert只能打印出object标示,却不能打印出来里面的内容,甚是不方便,于是各方面整理总结了如下一个函数,能够将数组或者对象这类的结果一一 ...
- js关于闭包的内存的问题--deep down
js有一个东西叫做GC(garbage collection )垃圾回收机制;js中有两种类型:js基本数据类型,js引用类型; 当一个函数[对象]--引用类型被引用后,过后,出了它的功能之后,gc会 ...
- Itext简绍及操作PDF文件
iText简介 iText是著名的开放源码的站点sourceforge一个项目,是用于生成PDF文档的一个java类库.通过iText不仅可以生成PDF或rtf的文档,而且可以将XML.Html文件转 ...
- 【HNOI 2017】大佬
Problem Description 人们总是难免会碰到大佬.他们趾高气昂地谈论凡人不能理解的算法和数据结构,走到任何一个地方,大佬的气场就能让周围的人吓得瑟瑟发抖,不敢言语.你作为一个 OIer, ...
- EasyMall注册功能
EasyMall注册功能 1. 环境搭建 创建一个EasyMall的web应用 配置www.easymall.com网站,并配置为缺省的虚拟主机,将EasyMall配 置为缺省的web应用,在配置in ...
- vue 双向数据绑定 Vue事件介绍 以及Vue中的ref获取dom节点
<template> <div id="app"> <h2>{{msg}}</h2> <input type="te ...
