用动态规划实现的最长公共子序列
#include<stdio.h>
#include<stdlib.h>
/*==============*\
|最长公共子序列
\*==============*/
/*!<打印最长公共子序列*/
void printLCS(char ** a,int m,int n,const char *s1, const char *s2)
{
int i,j;
if( m==1||n==1 )
{
if( a[m][n] == 1 )
printf("%c",s1[m-1]);
}
else if( a[m][n] == a[m][n-1] )
printLCS( a, m, n-1, s1, s2 );
else if( a[m][n] == a[m-1][n] )
printLCS( a, m-1, n, s1, s2 );
else
{
printLCS( a, m-1, n-1, s1, s2 );
printf("%c",s1[m-1]);
}
}
/*!<LCS算法*/
int LCS(const char *s1, const char *s2)
{// s1:0...m, s2:0...n
int m = strlen(s1), n = strlen(s2);
int i, j;
//--
char ** a;
a = (char**)malloc((m+1)*sizeof(char*));
for(i=0;i<m+1;i++)a[i]=(char*)malloc((n+1)*sizeof(char));
//--
for( i=1; i <= m; ++i )
a[i][0] = 0;
for( i=1; i <= n; ++i )
a[0][i] = 0;
for( i=1; i <= m; ++i )
for( j=1; j <= n; ++j )
{
if(s1[i-1]==s2[j-1])
a[i][j] = a[i-1][j-1]+1;
else if(a[i-1][j]>a[i][j-1])
a[i][j]= a[i-1][j];
else
a[i][j] = a[i][j-1];
}
//--
printLCS(a,m,n,s1,s2);
putchar('\n');
return a[m][n];
}
/*!< main*/
int main(void)
{
int m;
char * s1 = "178946546adfea54f6a4sd6a155";
char * s2 = "sdfa46879841a6asdfaa3dfa65a";
m = LCS( s1, s2 );
printf("%d\n",m);
system("pause");
return 0;
}
分享到:
相关推荐
最长公共子序列(Longest Common Subsequence,LCS)是一个经典的计算机科学问题,涉及序列比较和算法设计。在本实验报告中,我们将深入探讨如何利用动态规划方法解决这一问题。 首先,LCS问题旨在找到两个给定序列...
动态规划中的最长公共子序列 动态规划中的最长公共子序列是指给定两个序列 X 和 Y,找到他们的最长公共子序列的长度和该子序列本身。该问题是计算机科学中的一类典型问题,广泛应用于数据压缩、数据挖掘、生物信息...
最长公共子序列(Longest Common Subsequence,LCS)是一个经典的计算机科学问题,它涉及到序列比对和字符串处理。在两个或多个序列中,LCS是指没有改变原有顺序的情况下,存在于所有序列中的最长子序列。这个问题在...
### 最长公共子序列问题详解 #### 一、问题定义及背景 最长公共子序列(Longest Common Subsequence,简称LCS)问题属于计算机科学领域中的一个重要问题,尤其是在算法设计与分析方面。此问题的核心在于寻找两个...
实验报告的主题是“算法设计与分析”,关注的是使用动态规划解决最长公共子序列(Longest Common Subsequence, LCS)的问题。动态规划是一种有效的方法,它适用于具有最优子结构和子问题重叠性质的问题。在本实验中...
### 最长公共子序列算法总结 #### 一、O(n^2)算法 在讨论最长公共子序列(Longest Common Subsequence,简称LCS)问题时,通常会提及两种主要的算法实现方式:一种时间复杂度为O(n^2),另一种则通过优化达到O...
### C++实现最长公共子序列算法详解 在深入解析给定代码之前,我们先来了解一下“最长公共子序列”(Longest Common Subsequence,简称LCS)的基本概念及其在计算机科学中的应用。LCS问题是一种典型的动态规划问题...
【最长公共子序列(动态规划)】是一种经典的算法问题,主要应用于序列比对、文本处理等领域。本实验报告详尽地介绍了如何运用动态规划解决这一问题。 动态规划是一种解决复杂问题的有效方法,它通过将大问题分解为...
### 实验三:最长公共子序列 #### 实验目的 本次实验旨在使学生掌握如何运用动态规划策略来解决最长公共子序列(Longest Common Subsequence, LCS)问题,并通过编程实践加深对动态规划算法的理解。 #### 实验原理...
### 最长公共子序列动态规划算法 在计算机科学领域中,**最长公共子序列问题**(Longest Common Subsequence Problem, LCS)是一个经典的算法问题,它主要应用于文本比较、生物信息学中的DNA序列比对等领域。该问题...
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
最长公共子序列问题LCS 最长公共子序列问题(Longest Common Subsequence,LCS)是计算机科学中一个经典的问题,它是指给定两个序列X和Y,找出它们的最长公共子序列。该问题具有重要的理论和实际意义,在很多领域都...
### C++ 实现最长公共子序列问题 #### 知识点概述 本篇文章将详细介绍如何使用C++语言解决最长公共子序列(Longest Common Subsequence, LCS)问题,并结合具体的代码示例进行深入剖析。文章将涵盖以下几个核心...
最长公共子序列(Longest Common Subsequence,LCS)是计算机科学中一种经典的字符串问题,主要涉及算法设计和分析。它的目标是找到两个给定序列(通常为字符串)的最长子序列,该子序列在原序列中不需连续,但必须...
根据给定的文件信息,我们可以总结出以下关于“输出最长公共子序列”的C语言实现的知识点: ### 一、最长公共子序列问题介绍 最长公共子序列(Longest Common Subsequence,简称 LCS)是一个经典的计算机科学问题...
最长公共子序列(Longest Common Subsequence,LCS)问题是一个经典的计算机科学问题,主要涉及字符串处理和动态规划算法。在本场景中,我们使用C#编程语言来解决这个问题。C#是一种多范式编程语言,广泛应用于开发...