ZOJ 1733 Common Subsequence(LCS)
Common Subsequence
Time Limit: 2 Seconds Memory Limit: 65536 KB
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.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
分析:最长公共子序列
代码如下:
# include<stdio.h>
# include<string.h>
# define MAX
char s1[MAX],s2[MAX];
int dp[MAX][MAX];
int len1,len2;
int max(int a,int b,int c){
int temp;
temp = a>b ? a : b;
return temp>c ? temp : c;
}
int main(){
int i,j;
while(scanf("%s%s",s1,s2)!=EOF){
len1 = strlen(s1);
len2 = strlen(s2);
memset(dp,,sizeof(dp));
for(i=;i<=len1;i++){
for(j=;j<=len2;j++){
if(s1[i-] == s2[j-])
dp[i][j] = dp[i-][j-] + ;
dp[i][j] = max(dp[i][j],dp[i-][j],dp[i][j-]);
}
}
printf("%d\n",dp[len1][len2]);
}
return ;
}
最新文章
- phpstorm 配置 xdebug调试工具
- caffe的python接口学习(7):绘制loss和accuracy曲线
- psp进度(11月25号-31号)
- PADS在注册表中的菜单栏数据
- Effective Java 29 Consider typesafe heterogeneous containers
- 【ASP.NET 进阶】根据IP地址返回对应位置信息
- tomcat server.xml配置详解
- Spring MVC Controller 单元测试
- POJ 2109 :Power of Cryptography
- 关于oracle 还原数据库的要领
- golang fmt.printf()
- New UWP Community Toolkit - AdaptiveGridView
- Webpack 4教程:为什么要优化代码
- POJ滑雪
- python之路——20
- Django 的ORM 数据操作
- arcgis如何求两个栅格数据集的差集
- sql 一对多查询
- mysql学习笔记(三)
- service worker --- offline APP