题目大意:求两个字符串的最长公共子序列
题目思路:dp[i][j] 表示第一个字符串前i位 和 第二个字符串前j位的最长公共子序列
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAXSIZE 1005 using namespace std; char str1[MAXSIZE],str2[MAXSIZE]; int dp[MAXSIZE][MAXSIZE]; int main()
{
while(scanf("%s%s",str1+,str2+)!=EOF)
{
memset(dp,,sizeof(dp));
int len1=strlen(str1+);
int len2=strlen(str2+);
for(int i=;i<=len1;i++)
{
for(int j=;j<=len2;j++)
{
if(str1[i]==str2[j])
dp[i][j]=dp[i-][j-]+;
else
{
dp[i][j]=max(max(dp[i-][j],dp[i][j]),max(dp[i][j-],dp[i-][j-]));
}
}
}
printf("%d\n",dp[len1][len2]);
}
return ;
}
POJ 1458 Common Subsequence 最长公共子序列的更多相关文章
-
POJ 1458 Common Subsequence(最长公共子序列LCS)
POJ1458 Common Subsequence(最长公共子序列LCS) http://poj.org/problem?id=1458 题意: 给你两个字符串, 要你求出两个字符串的最长公共子序列 ...
-
POJ 1458 Common Subsequence 最长公共子序列 LCS
LCS #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> ...
-
PKU 1458 Common Subsequence(最长公共子序列,dp,简单)
题目 同:ZJU 1733,HDU 1159 #include <stdio.h> #include <string.h> #include <algorithm> ...
-
C++版 - Lintcode 77-Longest Common Subsequence最长公共子序列(LCS) - 题解
版权声明:本文为博主Bravo Yeung(知乎UserName同名)的原创文章,欲转载请先私信获博主允许,转载时请附上网址 http://blog.csdn.net/lzuacm. C++版 - L ...
-
lintcode 77.Longest Common Subsequence(最长公共子序列)、79. Longest Common Substring(最长公共子串)
Longest Common Subsequence最长公共子序列: 每个dp位置表示的是第i.j个字母的最长公共子序列 class Solution { public: int findLength ...
-
HDU 1159 Common Subsequence 最长公共子序列
HDU 1159 Common Subsequence 最长公共子序列 题意 给你两个字符串,求出这两个字符串的最长公共子序列,这里的子序列不一定是连续的,只要满足前后关系就可以. 解题思路 这个当然 ...
-
LCS(Longest Common Subsequence 最长公共子序列)
最长公共子序列 英文缩写为LCS(Longest Common Subsequence).其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已 ...
-
hdu 1159 Common Subsequence(最长公共子序列 DP)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1159 Common Subsequence Time Limit: 2000/1000 MS (Jav ...
-
LCS修改版(Longest Common Subsequence 最长公共子序列)
题目描述 作为一名情报局特工,Nova君(2号)有着特殊的传达情报的技巧.为了避免被窃取情报,每次传达时,他都会发出两句旁人看来意义不明话,实际上暗号已经暗含其中.解密的方法很简单,分别从两句话里删掉 ...
随机推荐
-
NOI 题库 7084
7084 迷宫问题 描述 定义一个二维数组: int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, ...
-
[SQL]SUTFF内置函数的用法
STUFF 删除指定长度的字符并在指定的起始点插入另一组字符. 语法 STUFF ( character_expression , start , length , character_express ...
-
JPA SQL 的复杂查询createNamedQuery
@NamedNativeQueries({ @NamedNativeQuery( name = "getNativeNutShellInfo", //需要调用的name query ...
-
C++:基类和派生类
4.1 派生类的声明 继承实例如下: class Person{ //声明基类Person public: void print() { cout<<"name:"&l ...
-
asp.net 下载任意格式文件 上传文件后台代码
思路:将文件转化为流,输出到页面上的iframe中去 //下载附件逻辑 object DownLoad(NameValueCollection nv) { int attachId = nv[&quo ...
-
Linux centOS本地DNS安装
centOS本地DNS安装 在centOS里最常用的DNS服务工具应该是bind了.下面就以bind为例做一个DNS服务. 首先查看bind 是否已经安装 Rpm -qa | gerp bind 如果 ...
-
如何看apache的版本号
在服务器上输入httpd -v就可以看到 在服务器上运行apachectl -v命令即可 Server version: Apache/2.2.3 Server built: Feb 25 2012 ...
-
idea Code激活
参考:http://blog.csdn.net/gnail_oug/article/details/70677272 1.将激活包复制到bin安装目录: 2.在安装的idea下面的bin目录下面有2个 ...
-
在python中使用正则表达式(一)
在python中通过内置的re库来使用正则表达式,它提供了所有正则表达式的功能. 一.写在前面:关于转义的问题 正则表达式中用“\”表示转义,而python中也用“\”表示转义,当遇到特殊字符需要转义 ...
-
Ubuntu 16.04下安装golang
手动安装 下载golang安装包 https://studygolang.com/dl 从上面的网站上下载适合自己机器的go版本,我这里选择的是go1.10.linux-386.tar.gz 解压安装 ...