用动态规划实现的最长公共子序列
#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)的问题。动态规划是一种有效的方法,它适用于具有最优子结构和子问题重叠性质的问题。在本实验中...