用动态规划实现的最长公共子序列
#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;
}
分享到:
相关推荐
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
最长公共子序列的两种算法简介,一种是平时最常见的算法,还有一种用滚动数组来做的。
最长公共子序列问题 最长公共子序列(动态规划) 实验数据:input.txt X={A,B,C,B,D,A,B}; Y={B,D,C,A,B,A} ——要求给出X、Y的最长公共子序列Z,程序运行结束时,将计算结果输出到文件output.txt中。输出文件中包含...
由此函数,把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段,第1阶段,按照式1计算X1和Yj的最长公共子序列长度L[1][j](1),第2阶段,按照2式计算X2和Yj的最长公共子序列长度L[2][j](1),...
C++求最长公共子序列!实用 花费了好长时间!!
算法导论实验 最长公共子序列程序源码 实验报告
最长公共子序列的算法实现,采用递归方法。
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
用Python实现动态规划中最长公共子序列和最长公共子串问题!
最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
实现了求最长公共子序列的算法,内容简单易懂,代码也很短