java实现最长连续子序列_最长公共子序列 ||
问题：在 前一篇文章 最长公共子序列 | 的基础上要求将所有的最长公共子序列打印出来，因为最长公共子序列可能不只一种。
难点：输出一个最长公共子序列并不难，难点在于输出所有的最长公共子序列，我们需要在动态规划表上进行回溯——从C[a][b]，即右下角的格子开始判断：
1） 如果格子C[i][j]对应的X[i-1] == Y[j-1]，则把这个字符放入 LCS 中，并跳入C[i-1][j-1]中继续进行判断；
2） 如果格子C[i][j]对应的X[i-1] ≠ Y[j-1]，则比较C[i-1][j]和C[i][j-1]的值，跳入值较大的格子继续进行判断;
3）直到 i 或 j 小于等于零为止，倒序输出 LCS 。如果出现C[i-1][j]等于C[i][j-1]的情况，说明最长公共子序列有多个，故两边都要进行回溯。
举下面这个例子：x[6]={'B','D','C','A','B','A'}, y[7]={'A','B','C','B','D','A','B'}
通过LCSLength函数我们可以得到C表：如下表所示。
从最右下角我们可以知道最长公共子序列的长度为4，（从0开始编号）从最右下角的元素开始，C[6][7]行列元素对应A!=B,所以不加到 lcs_str（最长公共子序列串），然后考虑C[6][7](行列元素相等)和C[5][7](行列元素相等)，而且C[6][7]大小等于C[5][7]，所以分别从C[6][7]和C[5][7]开始同样的操作，最后找到三条路径，如上图红线标注，对应为BCAB、BCBA、BDAB。
代码如下：
#include<iostream>
#include <fstream>
#include <cassert>
#include <string>
#include <sstream>
#include <set>
using namespace std;int c[100][100];
int d[100][100];
set<string> setOfLCS;string Reverse(string str)
{int low=0;int high=str.length()-1;while(low<high){char temp=str[low];str[low]=str[high];str[high]=temp;++low;--high;}return str;
}void LCSLength(int m,int n,char *x,char *y)
{int i,j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;d[i][j]=1;}else if(c[i-1][j]>c[i][j-1]){c[i][j]=c[i-1][j];d[i][j]=2;}else{c[i][j]=c[i][j-1];d[i][j]=3;}}}
}void traceBack(int i,int j,char *x,char *y,string lcs_str)
{while(i>0&&j>0){if(x[i]==y[j]){lcs_str.push_back(x[i]);--i;--j;}else{if(c[i-1][j]>c[i][j-1])--i;else if(c[i-1][j]<c[i][j-1])--j;else{traceBack(i-1,j,x,y,lcs_str);traceBack(i,j-1,x,y,lcs_str);return;}}}setOfLCS.insert(Reverse(lcs_str));
}void LCS(int i,int j,char *x)
{if(i==0||j==0)return;if(d[i][j]==1){LCS(i-1,j-1,x);cout<<x[i];}else if(d[i][j]==2)LCS(i-1,j,x);elseLCS(i,j-1,x);
}void readTxt(string file)
{ifstream infile;infile.open(file.data());assert(infile.is_open());string s;getline(infile,s);int n=atoi(s.c_str());int num=1;while(n--){getline(infile,s);istringstream tmp(s);tmp>>s;int a=atoi(s.c_str());tmp>>s;int b=atoi(s.c_str());getline(infile,s);istringstream t1(s);char x[a];char t;for(int i=1;i<=a;i++){t1>>t;x[i]=t;}for(int i=1;i<=a;i++)cout<<x[i]<<" ";cout<<endl;getline(infile,s);istringstream t2(s);char y[b];for(int i=1;i<=b;i++){t2>>t;y[i]=t;}for(int i=1;i<=b;i++)cout<<y[i]<<" ";cout<<endl;cout<<"Case "<<num++<<endl;LCSLength(a,b,x,y);cout<<c[a][b]<<" ";cout<<"LCS(X,Y):";//LCS(a,b,x);cout<<endl;string str;setOfLCS.clear();traceBack(a,b,x,y,str);set<string>::iterator beg = setOfLCS.begin();for( ; beg!=setOfLCS.end(); ++beg)cout << *beg << endl;for(int i=0;i<=b;i++){for(int j=0;j<=a;j++){cout<<c[j][i]<<" ";}cout<<endl;}}infile.close();
}int main()
{readTxt("input.txt");return 0;
}
txt文件输入如下：
运行结果如下：
相关文章：
替换元素和非替换元素的学习
替换元素和非替换元素的学习 (元素)[妙瞳] 引言 元素是文档结构的基础，在CSS中，每个元素生成了一个包含了元素内容的框（box,也翻译为“盒子”）。但是不同的元素显示的方式会有所不同，例如div和span不同，而s…
第十六天-企业应用架构模式-离线并发模式
1.乐观离线锁 （Optimistic Offline Lock） 运行机制 使用时机 例：领域层与数据层数据映射器 2.悲观离线锁 （Pessimistic Offline Lock） 运行机制 使用时机 例：简单锁管理对象 3.粗粒度锁 （Coarse…
hdu1518 bjfuoj1042 zoj1909 poj2362 经典的搜索加剪枝
bjfuoj的测试数据最水，用很简单的方法一下就过了，又调了好长时间，才过掉其它OJ上的这道题目~ /* * hdu1518/win.cpp * Created on: 2011-11-8 * Author : ben*/#include <cstdio>#include <cstdlib>#include <cstring>#…
投影参数_智能投影仪参数如何去看，其实很简单
我又来给大家安利投影仪了，毕竟用过的都知道有多刺激，但是估计很多人看到参数就头疼了吧？所以话不多说，直接上科普啦流明亮度流明怎么算的，家人们就不用详细了解了，只用记住，流明越高画面就越亮…
zoj 3554 A Miser Boss
题意：有a、b、c三个人同时工作，三个人做不同的任务需要不同的时间，但最后要求三个人做事情的总时间相同，输出做完所有任务需要的最少时间，如果无法达到三个人总工作时间相同，则输出“No” 当时一股脑筋觉着…
二进制_Kubernetes集群二进制部署
一、环境规划操作系统：CentOS7.4_x64kubernetes安装目录：/opt/kubernetes版本说明：Kubernetes：v1.9Docker：v17.12.0-ceEtcd：3.1二、安装Docker在所有节点执行：setenforce 0iptables -Fiptables …
delphi对窗体的查询(delphi xe2)
1、显示所有窗口的标题 2、根据关键字查询窗口 3、某一窗口内的所有控件及其内容 . unit Unit1;interfaceusesWinapi.Windows, Winapi.Messages, System.SysUtils, System.Variants,System.Classes, Vcl.Graphics,Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;typeTFo…
Buffer的工作方式
1、Buffer的工作方式 前面《java NIO的工作方式》介绍了Selector检测到通信信道I/O有数据传输时，通过select()方法取得SocketChannel，将数据读取或写入Buffer缓冲区，下面讨论Buffer如何接受和写出数据。通过查看JDK源码可知道，…
PHP 相关配置
2019独角兽企业重金招聘Python工程师标准>>> 1. php-fpm的pool 编辑php-fpm配置文件php-fpm.convim /usr/local/php/etc/php-fpm.conf //在[global]部分增加以下内容include etc/php-fpm.d/*.conf # 相当与Nginx的虚拟主机文件 “vhost” 的配置 创建存放pool配置…
学生教育云平台登录入口_湖南省教育云平台登录入口
湖南省教育云平台官方网站http://www.hnzyzx.com/，好学网的中小学频道为学友整理。 湖南省教育网： 点击登录： 湖南省教育云平台登录系统 下方为湖南信息教育云平台登录入口图示：安全教育平台学生姓名错误处理方法…
flash中制的SWC组件怎样导入到flex中使用
flash中制的SWC组件怎样导入到flex中使用2010-04-30 11:18在使用FLASH导出SWC组件文件后，放入项目的LIB文件夹，然后要用实例化一个对象才能进行时操作使用， 但要记得的是，导出时候要再导出的组件处勾选链接，勾选为AS导…
开源智能手机 Librem 5 跳票了，推迟至第3季度发布
百度智能云 云生态狂欢季 热门云产品1折起>>> 由 Purism 公司打造的开源智能手机 Librem 5 原计划于2019年4月正式发布。但根据官方最新的消息，Librem 5 将推迟至2019年第3季度发货。 根据之前的消息，Librem 5 的预售价为 599 美元。 Librem …
js 获取URL后面的参数
1、有时间由于缓存问题，用PHP可能就不是太好处理，所以可以用客户端进行URL的处理 如下：js 获取URL后面的参数 <script> function getUrlParam(name) { //获取url参数 var reg new RegExp("(^|&)" name "([^&…
机械键盘恢复出厂fn_黑爵毛茸茸系列机械键盘评测
写在前面之前试用过黑爵的巧克力键盘，给我留下了挺不错的使用体验，不仅外观设计上好看，原厂Cherry轴体手感也不错，这次有幸体验到黑爵新品毛茸茸系列键盘实属荣幸。开箱学弟这次拿到的键盘是Cherry青轴，可能是快递有些…
centos防火墙端口配置
增加防火墙配置，允许8080端口： # vi /etc/sysconfig/iptables 在允许ssh的下面增加一条： -A INPUT -m state --state NEW -m tcp -p tcp --dport 8080 -j ACCEPT 保存，重启iptables服务 ： # service iptables restart…
实时智能决策引擎在蚂蚁金服风险管理中的实践
摘要：以“数字金融新原力(The New Force of Digital Finance)”为主题，蚂蚁金服ATEC城市峰会于2019年1月4日上海如期举办。金融智能专场分论坛上，蚂蚁金服数据技术专家王修坤做了主题为《实时智能决策引擎在蚂蚁金服风险管理中的实践》的精彩…
JAVA如何检测GC日志
只需要在JAVA程序运行的时候，加上VM参数就可以。像下面这样: -XX:PrintGCDetails 更具体的请参考: http://flash520.blog.163.com/blog/static/34414475201063041157163/ 转载于:https://www.cnblogs.com/bestchenwu/archive/2011/11/26/9655409.html
eclipse c语言_如果你的电脑是windows7/10的环境，用什么编译器学习C语言好？
既然问题已经限制了Windows环境，那么就不再推荐Linux环境下的编译器了，虽然在Linux环境进行C语言的编程会比Windows可以更好的掌握一些基础知识，自己动手gcc,写makefile文件了解编译，链接的过程。下面对windows环境C语言开发IDE进…
Apache Tomcat 7.0.93 发布，开源 Java Web 应用服务器
Apache Tomcat 7.0.93 已发布，Tomcat 是 Java Servlet、JavaServer Pages、Java 表达式语言和 Java WebSocket 技术的开源实现，是一个免费的开放源代码的 Web 应用服务器。 与 7.0.92 相比，该版本包含许多 bug 修复和改进。有以下值得关注的变…
C# using 语法说明
using 关键字有两个主要用途： (一).作为指令，用于为命名空间创建别名或导入其他命名空间中定义的类型。 (二).作为语句，用于定义一个范围，在此范围的末尾将释放对象。using指令 ①允许在命名空间中使用类型，这样&…
多行表头_多行表头数据汇总你怎么操作？手动复制粘贴？OUT!用VBA1分钟完成
前景提要(文末提供源码下载)发现小伙伴们的数据结果真的好复杂，不昨天才分享过有多行表头的数据如何汇总合并，今天就有小伙伴反馈，他的数据虽然是有多行表头的，但是又有一些数据没有多行表头，那么在进行批量数据汇总的…
VirtualBox上Ubuntu 共享文件夹
1. virtualbox 菜单栏中设备--》共享文件夹，添加一个共享文件夹，比如共享文件夹路径是D:/share，共享文件夹名称是share。 2. 进入虚拟Ubuntu，在命令行终端输入： sudo mkdir /mnt/sharesudo mount -t vboxsf share /mnt…
tinyMCE
TinyMCE是一个轻量级的基于浏览器的所见即所得编辑器，由JavaScript写成。它对IE6和Firefox1.5都有着非常良好的支持。 功能方面虽然不能称得上是最强，但绝对能够满足大部分网站的需求，并且功能配置灵活简单。另一特点是加载速度非常快&#x…
监管大屏系统_高速公路监管系统大屏可视化
0x00 项目背景该项目用于高速公路监管。高速公路监管包括：高速公路的设备运行情况，设备维护情况，道路维护情况；交通流量分析，交通拥堵分析，拥堵溯源；事故分析，事件信息发布等。0x01设…
Android（java）学习笔记96：layout_weight使用注意事项
1. android:layout_weight使用说明： layout_weight是权重的意思，也就是各个控件所占的比重，用在LinearLayout布局中。当我们使用layout_weight的时候，layout_width和layout_height有三种表示方法 2. android:layout_weight使用之 …
41.uniq命令
uniq命令： 选项：-c:显示每行的重复次数；-u:仅显示未曾重复过的行；-d:仅显示重复过的行； 实例： 转载于:https://blog.51cto.com/itxuezhe/2354162
[JS-JQuery]基础
<noscript> If you see this message, your web browser doesnt support JavaScript or JavaScript is disabled. Please enable JavaScript in your browser settings so Newegg.com can function correctly.</noscript> $(tr:odd) //选择表格的奇数行$(div:visi…
位置偏移问题 绘制_AutoCAD教程之绘制螺栓连接组合图
螺栓、螺母是机械连接件中最为常用的标准件，螺栓连接通常需要组合在一起。下面我们以绘制螺栓连接组合件为例，学习在AutoCAD 2019中移动、复制、旋转等操作的应用方法。1. 新建文件及图层新建一个“无样板公制”文件，新建粗实线、细实线、中心…
spring mvc 控制器方法传递一些经验对象的数组
由于该项目必须提交一个表单，其中多个对象,更好的方法是直接通过在控制器方法参数的数组。 因为Spring mvc框架在反射生成控制方法的參数对象的时候会调用这个类的getDeclaredConstructor方法来获得构造函数, 可是一直报NoSuchMethodException的异常。 依据这种方法…