# POJ-1458 Common Subsequence（线性动规，最长公共子序列问题）

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 44464 Accepted: 18186 Description

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. Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. Output

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. Sample Input

abcfbc abfcab programming contest abcd mnp Sample Output

4 2 0

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <string>

using namespace std;
char s1[300];
char s2[300];
int dp[300][300];
int main()
{

while(scanf("%s%s",&s1,&s2)!=EOF)
{
int len1=strlen(s1);
int len2=strlen(s2);
memset(dp,0,sizeof(dp));
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(s1[i]==s2[j])
dp[i+1][j+1]=dp[i][j]+1;
else
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);

}
}
cout<<dp[len1][len2]<<endl;
}
return 0;
}

477 篇文章43 人订阅

0 条评论

## 相关文章

### HDUOJ----Coin Change

Coin Change Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 ...

28911

### hdu---(3555)Bomb(数位dp（入门）)

Bomb Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Jav...

3608

### POJ 2773 Happy 2006（容斥原理+二分）

Happy 2006 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 1...

3037

### HDU 1012 u Calculate e【暴力打表，水】

u Calculate e Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

2783

### HDUOJ---三角形(组合数学)

http://acm.hdu.edu.cn/showproblem.php?pid=1249 三角形 Time Limit: 2000/1000 MS (Ja...

3367

### HDU 2604 Queuing(矩阵快速幂)

Queuing Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (...

2583

### HDU-1520 Anniversary party（树形DP）

Anniversary party Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/...

2884

Key Task Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

3554

### poj-------------(2752)Seek the Name, Seek the Fame（kmp）

Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Tot...

2787

### HDUOJ ------1398

http://acm.hdu.edu.cn/showproblem.php?pid=1398 Square Coins Time Limit: 2000/100...

2806