文档章节

动态规划——最长公共子序列

曾劲松
 曾劲松
发布于 2016/03/29 14:56
字数 966
阅读 11
收藏 0

一个数列S,若分别是两个或多个已知序列的子序列,且是所有符合条件序列中最长的,则S称为已知序列的最长公共子序列。

最长公共子串:子串是串的一个连续的部分.

最长公共子序列:子序列则可以不必连续,而从序列中去掉任意的元素而获得新的序列

//只输出一个序列

#include<iostream>
#include<iostream>
#include<stdio.h>

using namespace std;
static const int max_int = 100;

void LCS(char* str1, char* str2, int m, int n, int c[max_int + 1][max_int + 1], int b[max_int + 1][max_int + 1]) {
	int i, j;
	for (i = 0; i <= m; i++) c[i][0] = 0;
	for (j = 1; j <= n; j++) c[0][j] = 0;
	for (i = 1; i <= m; i++) {
		for (j = 1; j <= n; j++) {
			if (str1[i-1] == str2[j-1]) {//这里下标容易错。
				c[i][j] = c[i - 1][j - 1] + 1;
				b[i][j] = 0;
			}
			else {
				if (c[i][j - 1]>c[i - 1][j]) {
					c[i][j] = c[i][j - 1];
					b[i][j] = -1;
				}
				else {
					c[i][j] = c[i - 1][j];
					b[i][j] = 1;
				}
			}
		}
	}
	cout << "最长公共子序列大小为:" << c[m][n] << endl;
}

void Display_LCS(int b[max_int + 1][max_int + 1], char* str1, int i, int j) {
	if (i == 0 || j == 0) return;
	if (0 == b[i][j]) {
		Display_LCS(b, str1, i - 1, j - 1);
		cout << str1[i - 1];
	}
	else if (-1 == b[i][j]) {
		Display_LCS(b, str1, i, j - 1);
	}
	else {
		Display_LCS(b, str1, i - 1, j);
	}

}

//不用递归,用个链表保存
void showLCS2(const vector<vector<int>> &d, const char *a, int m, int n) {
	list<char> ans;
	while (m > 0 && n > 0) {
			if (d[m][n] == 0) {
				ans.insert(ans.begin(),a[m]);
				--m;
				-n;
			}
			else if (d[m][n] == -1) {
				--n;
			}
			else {
				--m;
			}
	}
	for_each(ans.begin(), ans.end(), [](char a) {cout << a << endl;});
}

int main() {
	char str1[max_int];
	char str2[max_int];
	scanf("%s", str1);
	scanf("%s", str2);
	int m = strlen(str1);
	int n = strlen(str2);
	int c[max_int + 1][max_int + 1];
	int b[max_int + 1][max_int + 1];
	LCS(str1, str2, m, n, c, b);
	Display_LCS(b, str1, m, n);
	cout << endl;
	return 0;
}

如果要输出所有序列,请参考这篇博客。

str1[i-1]!=str2[j-1]且c[i-1][j]=c[j-1][i]的情况。

http://blog.chinaunix.net/uid-26548237-id-3374211.html

//求取所有的最长公共子序列
#include <iostream>
using namespace std;
 
 const int X = 100, Y = 100;        //串的最大长度
 char result[X+1];                    //用于保存结果
 int count=0;                        //用于保存公共最长公共子串的个数

 /*功能:计算最优值
  *参数:
  *        x:字符串x
  *        y:字符串y
  *        b:标志数组
  *        xlen:字符串x的长度
  *        ylen:字符串y的长度
  *返回值:最长公共子序列的长度
  *
  */
 int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen) 
 {
     int i = 0;
     int j = 0;

     int c[X+1][Y+1];
     for (i = 0; i<=xlen; i++) 
     {
         c[i][0]=0;
     } 
     for (i = 0; i <= ylen; i++ ) 
     {
         c[0][i]=0;
     }
     for (i = 1; i <= xlen; i++) 
     {
         
         for (j = 1; j <= ylen; j++) 
         {
             if (x[i - 1] == y[j - 1])
             {
                 c[i][j] = c[i-1][j-1]+1; 
                 b[i][j] = 1;
             }
             else 
                 if (c[i-1][j] > c[i][j-1]) 
                 {
                     c[i][j] = c[i-1][j]; 
                     b[i][j] = 2;
                 }
                 else 
                     if(c[i-1][j] < c[i][j-1])
                     {
                         c[i][j] = c[i][j-1]; 
                         b[i][j] = 3;
                     }
                     else
                     {
                         c[i][j] = c[i][j-1]; //或者c[i][j]=c[i-1][j];
                         b[i][j] = 4;
                     }
         }
     }
     cout << "计算最优值效果图如下所示:" << endl;
     for(i = 1; i <= xlen; i++)
     {
         for(j = 1; j < ylen; j++)
         {
             cout << c[i][j] << " ";
         }
         cout << endl;
     }
     return c[xlen][ylen];
 }
 
 /*功能:计算最长公共子序列
  *参数:
  *        xlen:字符串x的长度
  *        ylen:字符串y的长度
  *        x    :字符串x
  *        b:标志数组
  *        current_len:当前长度
  *        lcs_max_len:最长公共子序列长度
  *
  */
 void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_len,int lcs_max_len) 
 {
     if (i ==0 || j==0) 
     {
         for(int s=0; s < lcs_max_len; s++)
         {
             cout << result[s];
         }
         cout<<endl;
         count++;
         return;
     }
     if(b[i][j]== 1) 
     { 
         current_len--;
         result[current_len]=x[i- 1];
         Display_Lcs(i-1, j-1, x, b,current_len,lcs_max_len);
     }
     else 
     {
         if(b[i][j] == 2)
         {
             Display_Lcs(i-1, j, x, b,current_len,lcs_max_len);
         }
         else 
         {
             if(b[i][j]==3)
             {
                 Display_Lcs(i, j-1, x, b,current_len,lcs_max_len);
             }
             else
             {
                 Display_Lcs(i,j-1,x,b,current_len,lcs_max_len);
                 Display_Lcs(i-1,j,x,b,current_len,lcs_max_len);
             }
         }
     }
 }
 
 int main(int argc, char* argv[])
 {
     string x = "ABCBDAB";
     string y = "BDCABA";
     int xlen = x.length();
     int ylen = y.length();

     int b[X + 1][Y + 1];

     int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
     cout << lcs_max_len << endl;

     Display_Lcs( xlen, ylen, x, b, lcs_max_len, lcs_max_len );
     cout << "共有:" << count << "种";

  
     return 0;
 }

 

© 著作权归作者所有

上一篇: Data语义学
下一篇: 快速选择
曾劲松
粉丝 5
博文 200
码字总数 141434
作品 0
武汉
私信 提问
最长上升公共子序列(LICS)的O(nlogn)解法

$Longest$ $Increasing$ $Common$ $Subsequence$ 最长上升公共子序列 给定两个整数序列,写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . ....

白青sama
06/16
0
0
python实现最长公共子序列的求解

(待完善...) 最长公共子序列是动态规划基本题目,下面按照动态规划基本步骤解出来。 1.找出最优解的性质,并刻划其结构特征 序列a共有m个元素,序列b共有n个元素,如果a[m-1]==b[n-1],那么...

勉旃
2018/09/03
0
0
删除部分字符使其变成回文串问题——最长公共子序列LCS问题

先要搞明白:最长公共子串和最长公共子序列的区别。 最长公共子串(Longest Common Substirng):连续 最长公共子序列(Longest Common Subsequence,LCS):不必连续 题目:给定一个字符串s...

牧师-Panda
2016/09/10
676
0
动态规划算法之:最长公共子序列 & 最长公共子串(LCS)

1、先科普下最长公共子序列 & 最长公共子串的区别: 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共子串 其实这是一个序贯决...

大数据之路
2013/03/25
53.1K
2
有趣的算法问题之巧思妙想

有趣的算法 算法之所以有趣,在于他能够化繁为简,他能概括统御世间万物,将一个复杂的问题归结为一个非常简单的问题。其实所有高阶的算法,都可以用两个大的方法去解决,而且屡试不爽。分别...

Nicholas_Jela
2017/09/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
昨天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
昨天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部