最长公共子序列(LCS) Easy
2024-10-07 09:02:45
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Input
abcfbc abfcab
programming contest
abcd mnp
Output
4
2
0
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std;
const int N = + ;
int dp[N][N];
char str1[N], str2[N];
int main(){
while(scanf("%s %s", str1, str2) == ){
memset(dp, , sizeof(dp));
int len_1 = strlen(str1), len_2 = strlen(str2);
for(int i = ; i <= len_1; i++)
for(int j = ; j <= len_2; j++){
if(str1[i-] == str2[j-]) dp[i][j] = dp[i-][j-] + ;
else dp[i][j] = max(dp[i-][j], dp[i][j-]);
}
printf("%d\n", dp[len_1][len_2]);
}
}
最新文章
- angular2
- IE6实现图片或背景的圆角效果
- USB HID描述符【转】
- android studio使用发布者证书调试
- Topogun教学视频
- iOS-swift环形进度指示器+图片加载动画
- linux环境中 对tomcat配置java环境
- Linux散列表(一)——操作函数
- ViewData ViewBag ViewModel
- CentOS7--iptables的配置
- ps 如何裁切图片成一定的长宽高比例
- 开源三维地球GIS引擎Cesium常用功能的开发
- FMECA分析
- websocket-heartbeat-js心跳检测库正式发布
- Spring-----AOP-----事务
- Python1 简介及安装、基础
- Java全栈程序员之09:IDEA+GitHub
- Chap7:民间用语[《区块链中文词典》维京&;甲子]
- vmware 下linux 共享文件夹消失
- 网站首页多URL可访问,如何集中首页网站权重?
热门文章
- Winserver-禁止程序启动
- linux运维、架构之路-Logstash启动时指定jdk版本
- HDU 2546 饭卡(01背包)
- MySQL_DML操作
- Linux系统安装时分区的介绍
- windows powershell的常用命令
- Cannot connect to the Docker daemon. Is &#39;docker daemon&#39; running on this host?
- 后盾网lavarel视频项目---1、数据迁移
- SpringBoot(十二):SpringBoot整合Kafka
- leetcode 4寻找两个有序数组的中位数