最长公共子序列
① 求最长公共子序列（动态规划）
// 求LCS的长度
class LCS
{
public:
LCS(int nx, int ny, char *x, char*y); //创建二维数组c、s和一维数组a、b，并进行初始化
void LCSLength(); //求最优解值（最长公共子序列长度）
void CLCS(); //构造最优解（最长公共子序列）
……
private:
void CLCS(int i, int j);
int **c, **s.m, n;
char *a, *b;
};
int LCS::LCSLength()
{
for(int i=1; i<=m; i++) c[i][0]=0;
for(i=1; i<=n; i++) c[0][i]=0;
for (i=1; i<=m; i++)
for (int j=1; j<=n; j++)
if (x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1; s[i][j]=1; //由c[i-1][j-1]计算c[i][j]
}
else if (c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j]; s[i][j]=2; //由c[i-1][j]得到c[i][j]
}
else {
c[i][j]=c[i][j-1]; s[i][j]=3; //由c[i][j-1]得到c[i][j]
}
return c[m][n]; //返回最优解值
}
// 构造最长公共子序列
void LCS::CLCS(int i, int j)
{
if (i==0||j==0) return;
if (s[i][j]==1){
CLCS(i-1, j-1);
cout<<a[i];
}
else if (s[i][j]==2) CLCS(i-1, j);
else CLCS(i, j-1);
}
② 最长公共子序列的c++代码实现
//最大公共子序列
#include<iostream>
#include<string>
using namespace std;
void LCSLength(int m, int n, string &x, string &y,int ** c, int **b)
{
int i,j;
for( i=1;i<=m;i++) c[i][0]=0;
for( i=1;i<=n;i++) c[0][i]=0;
cout<<"111"<<endl;
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;
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
{
c[i][j] = c[i][j-1];
b[i][j]=3;
}
}
}
}
void LCS(int i, int j, string& x, int **b, string &result)
{
if(i==0 || j==0) return;
if(b[i][j] == 1)
{
LCS(i-1,j-1,x,b,result);
result+=x[i-1];
}
else
{
if(b[i][j] == 2)
LCS(i-1,j,x,b,result);
else
LCS(i,j-1,x,b,result);
}
}
string dp(string &x,string &y,string & result)
{
int m=x.size();
int n=y.size();
int **c=new int*[m+1];
for(int i=0;i<=m;i++)
c[i]=new int[n+1];
int **b=new int*[m+1];
for(int i=0;i<=m;i++)
b[i]=new int[n+1];
c[0][0]=0;
LCSLength(m, n, x, y, c, b);
LCS(m, n, x, b, result);
return result;
}
int main()
{
//
string x="find";
string y="fnid";
string result="";
dp(x,y,result);
cout<<x<<endl;
cout<<y<<endl;
cout<<result<<endl;
return 1;
}
③ 关于最长公共子序列输出的问题~~
“ABCBDAB”和“BDCABA”的最长公共子序列是BCBA？不对吧！
如果你想得到ABCB，看看下边：
#include <stdio.h>
#include <string.h>
void LcsLength(char *x,char *y,int m,int n,int c[][100],int b[][100])
{
puts(x);
puts(y);
int i,j;
for(i=0;i<=m;i++)
c[i][0]=0;
for(j=1;i<=n;j++)
c[0][j]=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;
b[i][j]=0;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=1;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=-1;
}
}
}
void PrintLCS(int b[][100], char *x, int i, int j)
{
if(i==0 || j==0)
return;
if(b[i][j]==0)
{
printf("%c",x[i-1]);//先输出，再递归
PrintLCS(b,x,i-1,j-1);
//printf("%c",x[i-1]);
}
else if(b[i][j]==1)
PrintLCS(b,x,i-1,j);
else
PrintLCS(b,x,i,j-1);
}
void main()
{
char x[100]={"ABCBDAB"};
char y[100]={"BDCABA"};
int c[100][100];
int b[100][100];
int m,n;
m=strlen(x);
n=strlen(y);
LcsLength(x,y,m,n,c,b);
printf("最长子序列为：");
PrintLCS(b,x,m,n);
printf("\n");
printf("最长子序列长度为：%d\n",c[m][n]);
}
因为你是先递归，再输出，所以输出是从内往外走（递归返回时输出）
如果你改为先输出再递归，这每递归一层就输出一个结果，递归返回时不再输出。
④ 求最长公共子序列的c语言代码
？？？
⑤ （算法 c++）动态规划法求解最长公共子序列 本人菜鸟求高手改错帮忙完成 谢谢了
不是我不想帮你，但如果真要改的话，整个程序差不多要重写了……首先你要确定此程序是上网刷题/比赛？还是自学算法知识？如果你有很好的数学功底还可以自学知识，但比赛的话自学是绝对不够的，那需要充分的交流，还有，养成良好的编程风格是一个极其重要的方面，在网上应该可以找到某些大牛的代码集，运气好还有注释版的，可以多多借鉴。下面是一段代码，NetBeans/G++编译通过，你可以尝试改成类结构的。^_^
#include <iostream>
using namespace std;
#define MAXLENGTH 20
// 这是偷懒的部分……不要介意哈
int maxLength[MAXLENGTH + 2][MAXLENGTH + 2];
int preChar[MAXLENGTH + 2][MAXLENGTH + 2];
/*
* 参数说明
* s1：待处理字符串1
* s2：待处理字符串2
* l1：s1长度（不包括字符串结束符'/0'）
* l2：s2长度（不包括字符串结束符'/0'）
*
* 参数中加const的目的是为了保护外部数据，防止因失误而在函数内部改变了本因无需改变的数值。
*/
int LCSLength(const char* s1, const int l1, const char* s2, const int l2) {
/* 尽量不要在for等语句中定义变量，每个函数一开始最好就把需要的变量全部定义好，同时尽量赋予有意义的函数名 */
/* 当然，有时偷点懒是可以的，但你要确保过了几个月后一看到代码就能很快知道这是啥意思 */
int i, j;
/* maxLength用于存放中间数据，意义：maxLength[i][j]表示：s1前i个字符与s2前j个字符的最长子序列长度
* preChar用于存放当前最长子序列是由那一个自序列得来的
* 因本算法特殊性，需要各额外2位的存储空间
*/
/**/
for (i = 0; i <= l1; i++) maxLength[i][0] = 0;
for (j = 0; j <= l2; j++) maxLength[0][j] = 0;
for (i = 0; i <= l1; i++)
for (j = 0; j <= l2; j++) {
/* 如果s1第i个字符与s2第j个字符相同，则更新maxLength[i+1][j+1]存储的最大值，和preChar存放的前缀自序列位置
* 下同
*/
if (s1[i] == s2[j] && maxLength[i + 1][j + 1] < maxLength[i][j] + 1) {
maxLength[i + 1][j + 1] = maxLength[i][j] + 1;
preChar[i + 1][j + 1] = 1;
}
if (maxLength[i + 1][j] < maxLength[i][j]) {
maxLength[i + 1][j] = maxLength[i][j];
preChar[i + 1][j] = 2;
}
if (maxLength[i][j + 1] < maxLength[i][j]) {
maxLength[i][j + 1] = maxLength[i][j];
preChar[i][j + 1] = 3;
}
}
/* 返回最长子序列长度 */
return maxLength[l1][l2];
}
/**
* s1、s2与上同
* i：s1当前字符序号
* j：s2当前字符序号
*
* i、j初始值为各自字符串长度
*/
void LCSOutput(const char* s1, const int i, const char* s2, const int j) {
if (i >= 0 && j >= 0) {
// 由于是逆向输出，所以先递归，后输出
switch (preChar[i][j]) {
case 1:
LCSOutput(s1, i - 1, s2, j - 1);
break;
case 2:
LCSOutput(s1, i - 1, s2, j);
break;
case 3:
LCSOutput(s1, i, s2, j - 1);
break;
default:
break;
}
if (s1[i] == s2[j])
cout << s1[i];
}
}
int main() {
cout << "最长公共子序列长度：" << LCSLength("1234567890", 10, "1358967", 7) << endl;
cout << "最长公共子序列（不确保唯一）：";
LCSOutput("1234567890", 10, "1358967", 7);
cout << endl;
return 0;
}
⑥ Pascal 最长公共子序列
varn,i,j:longint;
a,b,numa,numb:array[1..100000]oflongint;
procereqsrta(h,t:longint);
vari,j,k,x,y:longint;
begin
ifh>=tthenexit;
k:=random(t-h+1)+h;
x:=a[k];a[k]:=a[h];a[h]:=x;
y:=numa[k];numa[k]:=numa[h];numa[h]:=y;
i:=h;j:=t;
whilei<jdobegin
while(i<j)and(a[j]>x)dodec(j);
ifi<jthenbegina[i]:=a[j];numa[i]:=numa[j];inc(i);end;
while(i<j)and(a[i]<x)doinc(i);
ifi<jthenbegina[j]:=a[i];numa[j]:=numa[i];dec(j);end;
end;
a[i]:=x;numa[i]:=y;
qsrta(h,i-1);qsrta(i+1,t);
end;
procereqsrtb(h,t:longint);
vari,j,k,x,y:longint;
begin
ifh>=tthenexit;
k:=random(t-h+1)+h;
x:=b[k];b[k]:=b[h];b[h]:=x;
y:=numb[k];numb[k]:=numb[h];numb[h]:=y;
i:=h;j:=t;
whilei<jdobegin
while(i<j)and(b[j]>x)dodec(j);
ifi<jthenbeginb[i]:=b[j];numb[i]:=numb[j];inc(i);end;
while(i<j)and(b[i]<x)doinc(i);
ifi<jthenbeginb[j]:=b[i];numb[j]:=numb[i];dec(j);end;
end;
b[i]:=x;numb[i]:=y;
qsrtb(h,i-1);qsrtb(i+1,t);
end;
procereqsrtnumab(h,t:longint);
vari,j,k,x,y:longint;
begin
ifh>=tthenexit;
k:=random(t-h+1)+h;
x:=numa[k];numa[k]:=numa[h];numa[h]:=x;
y:=numb[k];numb[k]:=numb[h];numb[h]:=y;
i:=h;j:=t;
whilei<jdobegin
while(i<j)and(numa[j]>x)dodec(j);
ifi<jthenbeginnuma[i]:=numa[j];numb[i]:=numb[j];inc(i);end;
while(i<j)and(numa[i]<x)doinc(i);
ifi<jthenbeginnuma[j]:=numa[i];numb[j]:=numb[i];dec(j);end;
end;
numa[i]:=x;numb[i]:=y;
qsrtnumab(h,i-1);qsrtnumab(i+1,t);
end;
functionbfind(h,t,x:longint):longint;
varm:longint;
begin
ifh>tthenbfind:=h
elsebegin
m:=(h+t)div2;
ifx<numa[m]thenbfind:=bfind(h,m-1,x)
elsebfind:=bfind(m+1,t,x);
end;
end;
begin
randomize;
assign(input,'LCS.IN');reset(input);
assign(output,'LCS.OUT');rewrite(output);
read(n);
fori:=1tondoread(a[i]);
fori:=1tondoread(b[i]);
fori:=1tondobeginnuma[i]:=i;numb[i]:=i;end;
qsrta(1,n);
qsrtb(1,n);
qsrtnumab(1,n);
fori:=1tondonuma[i]:=maxlongint;
fori:=1tondobegin
j:=bfind(1,n,numb[i]);
numa[j]:=numb[i];
end;
j:=bfind(1,n,maxlongint-1);
writeln(j-1);
close(output);close(input);
end.
⑦ 求最长公共子序列的C语言程序
得到字符串m1,m2后，有一个为空则子列为空。
如果都不为空，开始下面的步骤。
求得两列的长度分别为n1,n2。
动态生n2行n1列矩阵（二维数组）。
取m2中每个元素（记位置为i）与m1中元素（记位置为j）逐个比较，如果相等则为矩阵中相应行列坐标的元素赋值为1，否则为0（可用循环嵌套完成）。
比如m1(abc0cbad)m2(cba1abc)两串的话，可以得到如图所示矩阵。
然后，不难看出，要进行如下步骤。
定义max,用来记录最大子列中元素个数。
定义数组l[n2],用来记录最大子列的首字符地址（因为可能有不同最大子列，故用数组，而不是单个变量）。
判断矩阵中每一个元素，是否为1，如果是则记下此时行地址到l数组，然后判断相对于这个元素的下一行下一列的元素是否为1，如果是则继续判断，一直到为0。记下此次判断（即一个while循环）中“1”的个数n，存入变量max。
对于矩阵中的每一个元素都这么判断，如果判断中n的值大于max那么把n付给max，同时把这个子列的首地址付给l[0]，l[0]后面的元素全赋值为-1。如果，某次判断得到的n与max相同，即有相同最大子列，那么把它的首地址存入l数组的下一个位置。
当这个矩阵的每一个元素都判断完毕后，会得到max,和数组l，然后用循环做如下输出过程：依次以l数组中的每个元素为首地址，输出m2字符串中以相应序号开头的max个字符，那么完成所有最大子列的输出。
昨天失眠了，一直到今天凌晨3点多，脑袋浑浑噩噩的，本想帮你敲代码，可是脑力不支了，估计敲出来也乱，还有问题的话，再讨论452032545
⑧ java怎么写求最长的公共子序列
/*目标：输出两个字符串的所有公共最长子序列date:09-11-26BY:zggxjxcgx算法：判断较短串是否为较长串的子序列，如果是则得到结果；否则，对较短串进行逐个字符删除操作（将字符替换为'#'表示删除）。删除操作用递归函数进行实现。每层递归删除一个字符，若删除一个字符后未得到匹配子序列，则还原该字符所在位置。第n层递归未找到匹配子序列，则将递归层数加1，重复删除直到剩下空串。*/#include#includeintdep=0;/*较短串的长度*/intdepflag=0;/*下一步要探测的深度*/intlastflag=0;/*是否找到匹配子序列，1为找到*/intcount=0;/*目标结果的个数*/intmystrcmp(char*s1,char*s2)/*判断s2是否为s1的子串*/{while(*s1*s2)if(*s2=='#')s2++;elseif(*s2==*s1){s1++;s2++;}elses1++;while(*s2=='#')s2++;if(*s2=='\0')return1;return0;}voidpristr(char*str)/*打印最长子序列*/{if(0==count++)printf("\n公共最长子序列：\n");printf("%2d:",count);while(*str){if(*str!='#')printf("%c",*str);str++;}printf("\n");}/*递归函数求最长子序列。start控制下一个要检测的字符,deptemp控制递归的深度,first为's'表示第一层递归*/intfun(char*str1,char*str2,char*start,intdeptemp,charfirst){inti=0,j=0;char*s,cback;do{s=start;if('s'==first)deptemp=depflag;/*在第一层设置递归深度*/while(*s){if(*s=='#'){s++;continue;}cback=*s;*s='#';/*删除当前字符*/if(mystrcmp(str1,str2)){pristr(str2);lastflag=1;}/*找到匹配，将lastflag设为1，在完成深度为deptemp+1的探测（找到所有匹配）后退出递归*/elseif(deptemp>0)fun(str1,str2,s+1,deptemp-1,'n');/*深度探测，s+1表示从下一个位置开始删除*/*s=cback;s++;/*还原该位置的字符，以便下次进行探测*/}if('s'==first)++depflag;/*删除depflag+1个字符还未找到，则递归深度加1*/}while(depflagstrlen(st2))s1=st1,s2=st2;/*将s1设为较长的串*/elses1=st2,s2=st1;printf("\nstr1:%s\nstr2:%s\n",s1,s2);dep=strlen(s2);/*得到较短串的长度*/if(mystrcmp(s1,s2))pristr(s2);elseif(0==fun(s1,s2,s2,0,'s'))printf("\n没有公共元素！\n");//printf("%d\n",mystrcmp("afdebjewcwedw","abcdw#"));}
⑨ 求数组的最大子数组值和最长公共子序列问题
a) 最长公共子序列的结构
若用穷举搜索法，耗时太长，算法需要指数时间。
易证最长公共子序列问题也有最优子结构性质
设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>，则：
i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
iii. 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。
最长公共子序列问题具有最优子结构性质。
⑩ 最长公共子串和最长公共子序列的区别
/* 目标：输出两个字符串的所有公共最长子序列
date: 09-11-26
BY: zggxjxcgx
算法： 判断较短串是否为较长串的子序列，如果是则得到结果；
否则，对较短串进行逐个字符删除操作（将字符替换为'#'表示删除）。
删除操作用递归函数进行实现。每层递归删除一个字符，
若删除一个字符后未得到匹配子序列，则还原该字符所在位置。
第n层递归未找到匹配子序列，则将递归层数加1，重复删除直到剩下空串。
*/
#include<stdio.h>
#include<string.h>
int dep=0; /* 较短串的长度 */
int depflag=0; /*下一步要探测的深度 */
int lastflag=0; /* 是否找到匹配子序列，1为找到 */
int count=0; /* 目标结果的个数 */
int mystrcmp(char *s1,char *s2) /* 判断s2是否为 s1的子串 */
{ while(*s1 *s2)
if(*s2=='#') s2++;
else if(*s2 == *s1) { s1++; s2++; }
else s1++;
while(*s2=='#') s2++;
if(*s2=='\0') return 1;
return 0;
}
void pristr(char *str) /* 打印最长子序列 */
{ if(0==count++) printf("\n公共最长子序列：\n");
printf("%2d:",count);
while(*str)
{ if(*str!='#')
printf("%c",*str);
str++;
}
printf("\n");
}
/*递归函数求最长子序列。start 控制下一个要检测的字符,deptemp控制递归的深度,first为's'表示第一层递归 */
int fun(char *str1,char *str2,char *start,int deptemp,char first)
{ int i=0,j=0;
char *s,cback;
do
{ s=start;
if('s'==first) deptemp=depflag; /* 在第一层设置递归深度 */
while(*s)
{ if(*s=='#') { s++; continue; }
cback=*s; *s='#'; /* 删除当前字符*/
if(mystrcmp(str1,str2)) { pristr(str2); lastflag=1; } /*找到匹配，将lastflag设为1，在完成深度为deptemp+1的探测（找到所有匹配）后退出递归 */
else if(deptemp>0) fun(str1,str2,s+1,deptemp-1,'n'); /* 深度探测，s+1表示从下一个位置开始删除 */
*s=cback; s++; /* 还原该位置的字符，以便下次进行探测 */
}
if('s'==first) ++depflag; /* 删除depflag+1个字符还未找到，则递归深度加1 */
}while(depflag<dep-1 's'==first 0==lastflag); /* 第一层递归具有特殊意义，由三个变量标记是否第一层 */
if(lastflag) return 1; /* lastflag 为1 表示找到匹配子序列 */
return 0;
}
void main()
{ char *s1,*s2;
char st1[]="asfdebjewcwedwk";
char st2[]="sabscdkwss"; // kwfsa
if(strlen(st1)>strlen(st2)) s1=st1,s2=st2; /* 将s1设为较长的串 */
else s1=st2,s2=st1;
printf("\nstr1:%s\nstr2:%s\n",s1,s2);
dep=strlen(s2); /* 得到较短串的长度 */
if(mystrcmp(s1,s2)) pristr(s2);
else if(0==fun(s1,s2,s2,0,'s')) printf("\n没有公共元素！\n");
// printf("%d\n",mystrcmp("afdebjewcwedw","abcdw#"));
}