HDU - 1159 Common Subsequence (最长公共子序列)
2024-09-03 18:31:44
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 <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
#define N 1005
int dp[N+][N+];
char str1[N],str2[N];
int lcs(int len1,int len2)
{
int i,j;
int len=max(len1,len2);
for(i=;i<=len;i++){
dp[i][]=;
dp[][i]=;
}
for(i=;i<=len1;i++){
for(j=;j<=len2;j++){
if(str1[i-]==str2[j-]){
dp[i][j]=dp[i-][j-]+;
}
else {
dp[i][j]=max(dp[i][j-],dp[i-][j]);
}
}
}
return dp[len1][len2];
}
int main()
{
while(cin>>str1>>str2){
int len1=strlen(str1);
int len2=strlen(str2);
cout<<lcs(len1,len2)<<endl;
}
return ;
}
最新文章
- 程序员装B指南
- javax.el.PropertyNotFoundException 出错
- c# 反射类字段
- Python计算斗牛游戏的概率
- UpdatePanel中执行js
- lower_bound()函数
- Jtree (节点的渲染+资源管理器)
- struct2(一)第一个struct程序
- 使用navicat连接远程linux的mysql中文显示乱码的问题
- Ansible 变量
- 4、js内置函数
- 微信小程序模板消息详解
- TCP 粘包问题浅析及其解决方案
- Introduction to debugging neural networks
- [转] 在安卓设备上使用 Chrome 远程调试功能
- 数据库,ADO.NET(ADO),Oledb(Odbc)和编程语言关系框架图
- Windows7共享设置
- js写的一些通用方法
- BZOJ4922 Karp-de-Chant Number(贪心+动态规划)
- [ACM] ZOJ Martian Addition (20进制的两个大数相加)