文档章节

最长连续子序列(continuous LCS)

RLRL
 RLRL
发布于 2014/05/26 13:27
字数 245
阅读 22
收藏 0
#include <iostream>
#include <string.h>
#include <assert.h>
#include <stdio.h>
using namespace std;

int c[100][100];

//LCS-LENGTH
static int* LCS_LENGTH(char* X, char* Y)
{
	
	int m = strlen(X);
	int n = strlen(Y);

	int i = 0;
	int j = 0;
	int cmax = -100;
	for (i = 0; i <= m; i++)
	{
		c[i][0] = 0;
	}
	for (i = 0; i <= n; i++)
	{
		c[0][i] = 0;
	}

	int lcs_pos = 0;
	for (i = 1; i <= m; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if(X[i-1] == Y[j-1])
			{
				c[i][j]  = c[i-1][j-1] + 1;
			}
			else
			{
				c[i][j] = 0;
			}

			if(c[i][j] > cmax)
			{
				lcs_pos = i;//the position related to the max length
				cmax = c[i][j];//record the max length
			}
		}
	}

	cout << "cmax :"<< cmax << "  lcs_pos :" << lcs_pos << endl;

	int *para = new int[2];
	para[0] = cmax;
	para[1]= lcs_pos;
	return para;
}

//construct the result
static void PRINT_LCS(char* X, char* Y)
{

	int *para = LCS_LENGTH(X, Y);
	int k = para[0], pos = para[1];

	char* lcs = new char[ k + 1 ];
	assert( lcs != NULL);

	lcs[k] = '\0';

	while( k > 0)
	{
		lcs[--k] = X[ pos- 1 ];
		pos--;

	}

	cout << "LCS is : " << lcs << endl;
}

//test
int main(void)
{
	char X[ ] = "ABCBDBABCFS";
	char Y[ ] = "BDBCBDCABCFS";

	cout << "X : " << X << endl << "Y : " << Y << endl;
	PRINT_LCS(X, Y);

	cout << endl;

	return 0;
}


© 著作权归作者所有

RLRL
粉丝 13
博文 18
码字总数 10318
作品 0
嘉定
程序员
私信 提问
最长公共子序列(LCS)

最长公共子序列,即Longest Common Subsequence,LCS。一个序列S任意删除若干个字符得到新序列T,则T叫做S的子序列;两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序...

klaus丶
2016/02/24
46
0
动态规划算法之:最长公共子序列 & 最长公共子串(LCS)

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

大数据之路
2013/03/25
53.4K
2
LCS 算法:Javascript 最长公共子序列

最长公共子序列(Longest Common Subsequence LCS)是从给定的两个序列X和Y中取出尽可能多的一部分字符,按照它们在原序列排列的先后次序排列得到。LCS问题的算法用途广泛,如在软件不同版本...

技术小能手
2018/07/23
0
0
动态规划之两个字符串的最大子序列

1、问题 求两个字符串的最大子序列 1)、子序列和子字符串有区别,子字符串(子串)必须连续,列如 s1 = "ABCDAB" s2= "BBCDAAB" s1和s2最大子序列有"BCDA","BCDB", "CDAB","ABAB","BCAB"........

u011068702
2018/03/24
0
0
算法与数据结构(二):动态规划(DP)总结

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/89388883 1. 最长公共子序列 题目描...

dby_freedom
04/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

可见性有序性,Happens-before来搞定

写在前面 上一篇文章并发 Bug 之源有三,请睁大眼睛看清它们 谈到了可见性/原子性/有序性三个问题,这些问题通常违背我们的直觉和思考模式,也就导致了很多并发 Bug 为了解决 CPU,内存,IO ...

tan日拱一兵
34分钟前
3
0
网络七层模型与TCP/UDP

为了使全球范围内不同的计算机厂家能够相互之间能够比较协调的进行通信,这个时候就有必要建立一种全球范围内的通用协议,以规范各个厂家之间的通信接口,这就是网络七层模型的由来。本文首先...

爱宝贝丶
37分钟前
4
0
Jenkins World 贡献者峰会及专家答疑展位

本文首发于:Jenkins 中文社区 原文链接 作者:Marky Jackson 译者:shunw Jenkins World 贡献者峰会及专家答疑展位 本文为 Jenkins World 贡献者峰会活动期间的记录 Jenkins 15周岁啦!Jen...

Jenkins中文社区
55分钟前
10
0
杂谈:面向微服务的体系结构评审中需要问的三个问题

面向微服务的体系结构如今风靡全球。这是因为更快的部署节奏和更低的成本是面向微服务的体系结构的基本承诺。 然而,对于大多数试水的公司来说,开发活动更多的是将现有的单块应用程序转换为...

liululee
今天
8
0
OSChina 周二乱弹 —— 我等饭呢,你是不是来错食堂了?

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @ 自行车丢了:给主编推荐首歌 《クリスマスの夜》- 岡村孝子 手机党少年们想听歌,请使劲儿戳(这里) @烽火燎原 :国庆快来,我需要长假! ...

小小编辑
今天
1K
13

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部