博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
TOJ 1139.Compromise
阅读量:5830 次
发布时间:2019-06-18

本文共 2061 字,大约阅读时间需要 6 分钟。

2015-06-03

问题简述:

  大概就是输入两段文本(用小写英文字母表示),分别用#表示一段话的结束输入,输出这两个文本的最长公共子序列。

  简单的LCS问题,但是输入的是一段话了,而且公共部分比较是字符串的比较。

  原题链接:

解题思路:

  简单的最长公共子序列问题,只不过过程中比较的是两个字符串,故使用二维字符数组保存输入文本。

  输入 x[1...m][], y[1...n][] ,c[i,j]代表两个文本的LCS的长度,递归方程如下:

  c[0,j] = c[i,0] = 0;

  c[i,j] = c[i-1,j-1] + 1               if x[i]==y[j]

  c[i,j] = max(c[i-1,j], c[i,j-1])    if x[i]!=y[j]

    使用 b[i,j] 表示三种情况(=1,=2,=3),方便以后输出LCS:

    if b[i,j] == 1,表示 x[i] == y[j], 可以输出;

    if b[i,j] == 2,表示 c[i-1,j] > c[i,j-1], i--即可;

    if b[i,j] == 3,表示 c[i,j-1] > c[i-1,j], j--即可;

源代码:

1 /* 2 OJ: TOJ 3 ID: 3013216109 4 TASK: 1139.Compromise 5 LANG: C++ 6 NOTE: LCS(DP) 7 */ 8 #include 
9 #include
10 using namespace std;11 12 int main()13 {14 char x[105][31],y[105][31],ans[105][31];15 int c[105][105],b[105][105];16 int i,j,k,m,n;17 while(cin >> x[1]) {18 for(i=2;;i++) {19 cin >> x[i];20 if(x[i][0]=='#')break;21 }22 for(j=1;;j++) {23 cin >> y[j];24 if(y[j][0]=='#')break;25 }26 m=i-1; n=j-1;27 for(i=0;i<=m;i++)28 c[i][0]=0;29 for(i=1;i<=n;i++)30 c[0][i]=0;31 for(i=1;i<=m;i++) {32 for(j=1;j<=n;j++) {33 if(!strcmp(x[i],y[j])) {34 c[i][j]=c[i-1][j-1]+1;35 b[i][j]=1;36 }37 else if(c[i-1][j]>=c[i][j-1]) {38 c[i][j]=c[i-1][j];39 b[i][j]=2;40 }41 else {42 c[i][j]=c[i][j-1];43 b[i][j]=3;44 }45 }46 }47 i=m;j=n;48 k=c[m][n]-1;49 while(i>0&&j>0&&k>=0) {50 if(b[i][j]==1) {51 strcpy(ans[k],x[i]);52 i--;j--;k--;53 }54 else if(b[i][j]==2) i--;55 else if(b[i][j]==3) j--;56 else break;57 }58 for(i=0;i

 

转载于:https://www.cnblogs.com/ACMans/p/4550661.html

你可能感兴趣的文章
云计算最大难处
查看>>
关于数据分析思路的4点心得
查看>>
Memcached安装与配置
查看>>
美团数据仓库的演进
查看>>
SAP被评为“大数据”预测分析领军企业
查看>>
联想企业网盘张跃华:让文件创造业务价值
查看>>
记录一次蚂蚁金服前端电话面试
查看>>
直播源码开发视频直播平台,不得不了解的流程
查看>>
Ubuntu上的pycrypto给出了编译器错误
查看>>
聊聊flink的RestClientConfiguration
查看>>
在CentOS上搭建git仓库服务器以及mac端进行克隆和提交到远程git仓库
查看>>
測試文章
查看>>
Flex很难?一文就足够了
查看>>
【BATJ面试必会】JAVA面试到底需要掌握什么?【上】
查看>>
CollabNet_Subversion小结
查看>>
mysql定时备份自动上传
查看>>
Linux 高可用集群解决方案
查看>>
17岁时少年决定把海洋洗干净,现在21岁的他做到了
查看>>
linux 启动oracle
查看>>
《写给大忙人看的java se 8》笔记
查看>>