连接: http://acm.nyist.net/JudgeOnline/problem.php?pid=36
最长公共子序列
时间限制:3000 ms | 内存限制:65535 KB
难度:3
tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于1000.
2 asdf adfsd 123abc abc123abc
3 6
动态规划:p[i][j]表示第一个串的第i个和第二个串的j比较时的最优解
如果 str1[i]==str2[j] 则p[i][j]=p[i-1][j-1]+1;
否则 p[i][j]=max( p[i-1][j] , p[i][j-1] );
然后 p[len1][len2]就是要求的结果啦!
#include<string.h> #include<stdio.h> #define max(a,b) a>b?a:b int p[1010][1010]; int main() { int T,i,j,len1,len2; char str1[1010]; char str2[1010]; scanf("%d",&T); while(T--) { memset(p,0,sizeof(p)); scanf("%s%s",str1,str2); len1=strlen(str1); len2=strlen(str2); for(i=0;i<len1;i++) { for(j=0;j<len2;j++) { if(str1[i]==str2[j])p[i+1][j+1]=1+p[i][j]; else p[i+1][j+1]=max(p[i][j+1],p[i+1][j]); } } printf("%d\n",p[len1][len2]); } return 0; }
这种方法比较笨拙,因为在比较第一个串的第i个时,第二个串只需用到p[i-1][j]或者p[i][j] (j:1~len2)这两行数,而上面却用到了len1*len2的二维数组,下面的方法是运用滚动数组来优化。可以省下大量的时间和空间(建议在可以看懂第一种的前提下在看这种方法)
#include <stdio.h> #include <string.h> #define max(a,b) (a)>(b) ? (a) : (b) char a[1005], b[1005]; short int up[1005], dab[1005];//up存放上一行的数,dad存放新一行的数 short int t, la, lb; int dp(void) { int i, j; memset(up, 0, sizeof(up)); memset(dab, 0, sizeof(dab)); for (i = 0; i < la; i++)//两个循环还是一样 { for (j = 0; j < lb; j++) { if (a[i] == b[j])//如果第一个串的第i个和第二个串的第j个相等 dab[j+1] = up[j]+1;//就在上一行j-1的基础上加1 else dab[j+1] = max(up[j+1], dab[j]);//否则就取上一行的第j个位置和这一行的第j-1的位置的最大值 } for (j = 0; j <= lb; j++)//数组滚动,更新上一行的数组 up[j] = dab[j]; } return dab[lb];//返回结果 } int main() { scanf("%hd", &t); while (t--) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); scanf("%s%s", a, b); la = strlen(a); lb = strlen(b); printf("%hd\n", dp()); } return 0; }
题到此也就告一段落了,但仔细想想,上面的方法其实还是可以在次优化的,每次在找p[i][j]时,用到的只有p[i-1][j-1] 、p[i][j-1] 、 p[i-1][j] 这些值,我们找个变量把它们存起来就好了,如果只用一个数组p[j]在写
p[i-1][j]和p[i][j]其实就是p[j]一个人,只不过是在更新之前当做p[i-1][j]用,更新之后就变成了p[i][j],大家慢慢体会吧、
下面这种做法又优化了大量的时间和空间
#include <cstdio> #include<cstring> #define max(x,y) x>y?x:y char a[1005],b[1005]; int f[1005]; int main() { int T,la,lb,k,k1,i,j; scanf("%d",&T); while(T--) { memset(f,0,sizeof(f)); scanf("%s%s",a,b); la=strlen(a); lb=strlen(b); for(i=0;i<la;i++) for(j=0,k1=0;j<lb;j++) { k=f[j+1];//k保存上一行的第j个位置的值 if(a[i]==b[j]) f[j+1]=k1+1; else if(f[j]>f[j+1]) f[j+1]=f[j];//f[j+1]有双重的身份,比较前是上一行的值,比较后就是新一行的值啦!慢慢理解吧 k1=k;//k1保存上一行的个j-1个位置的值 } printf("%d\n",f[lb]); } }
相关推荐
南阳理工oj离线题库
南阳理工学院OJ第1版解题报告V1.0.pdf
南阳理工学院OJ_个人AC代码包(Java提交) 是Java初学者登堂入室的很好例子。
这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 6 1 8 3 6 5 9 5 1 2 3 4 5 0 输出样例 4 4 5 提示 一,对输入...
南阳理工学院stl练习场全部ac代码!
算法设计与分析 最大公共子序列问题 。
南阳理工ACM离线题库
哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案哈理工OJ1084答案
结课实习中做的一个小程序,是关于数据结构中最长公共子系列的算法 能运行……
西安理工大学学生在线实验系统编程题答案(超级详细)
山东理工大学2016级OJ进程,始于悦行,终于诚信。
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip
趣味题:柱状图排序 西安理工大学学生在线实验系统 oj
山东理工大学2016级OJ题目1833
湖南理工学院OJ的0-100题解.rar
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
山东理工大学2016级OJ题目1834
搭建OJ平台的工具,方便大家搭建自己的OJ,建议大家使用ubuntu14.04版本,比较稳定
OJ习题.zip
厦门理工学院软件工程重点课件,考试前抱佛脚可用。