hdu 1503, LCS variants, find a LCS, not just the length, backtrack to find LCS, no extra markup 分类: hdoj 2015-07-18 16:24 139人阅读 评论(0) 收藏
2024-09-15 17:14:01
a typical variant of LCS algo.
the key point here is, the dp[][] array contains enough message to determine the LCS, not only the length, but all of LCS candidate, we can backtrack to find all of LCS.
for backtrack, one criteria is
dp[i-1][j]==dp[i][j]-1 && dp[i][j-1]==dp[i][j]-1
another is
dp[i][j]==dp[i-1][j-1]+1 && str1[i]==str2[j]
both is ok, here the first one is used.
//
#include <cstdio>
#include <cstring>
#include <algorithm>
struct myNode{ int x,y; };
#define MAXSIZE 105
int dp[MAXSIZE][MAXSIZE];
myNode pos[MAXSIZE];
char str1[MAXSIZE], str2[MAXSIZE];
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int i,j,k,ch,len1,len2,len3;
while(scanf("%s%s",str1+1, str2+1)==2) {
len1=strlen(str1+1), len2=strlen(str2+1);
for(i=1;i<=len1;++i) {
for(ch=str1[i], j=1;j<=len2;++j) {
if(ch==str2[j]) dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=std::max(dp[i][j-1],dp[i-1][j]);
}
}
for(i=len1, j=len2, len3=dp[len1][len2]-1;len3>=0;--len3) {
while(1) {
for(k=j;len3!=dp[i][k-1];--k) {}
if(len3==dp[i-1][k]) {
pos[len3]={i,k};
--i, j=k-1;
break;
}
else {
--i;k=j;
}
}
}
len3=dp[len1][len2];
pos[len3]={len1+1,len2};
for( i=1, j=1, k=0;k<=len3;++k,++i,++j) {
for(;i<pos[k].x;++i) putchar(str1[i]);
for(;j<pos[k].y;++j) putchar(str2[j]);
putchar(str2[j]);
}
putchar('\n');
}
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。// p.s. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.
最新文章
- mariadb 10.2.3支持oracle execute immediate语法
- nginx https反向代理 tomcat
- 取消 virtualStore 注册表[启用和禁止 UAC虚拟化]
- python 数字、字符串、列表常用函数
- POJ 2184 Cow Exhibition (01背包的变形)
- PHP设计模式浅析
- 第一篇、HTML标签
- ORA-01461: 仅能绑定要插入 LONG 列的 LONG 值
- android下面res目录
- LeetCode 292. Nim Game (取物游戏)
- DSAPI 网页获取本地程序登陆用户
- 【转】重写Equals为什么要同时重写GetHashCode
- 基于设备树的controller学习(2)
- go 学习 ---golang命令
- 腾讯高性能RPC开发框架Tars实现服务治理(微服务)
- BZOJ1004 HNOI Cards
- [BZOJ3143][HNOI2013]游走(期望+高斯消元)
- 硬件PCB Layout布局布线Checklist检查表(通用版)
- JSTL <;c:if test=“eq ne lt..”>;<;/if>; 用法
- 洛谷P1196 [NOI2002]银河英雄传说(带权并查集)