最長公共子序列演算法

① 最長公共子串和最長公共子序列的區別

/* 目標：輸出兩個字元串的所有公共最長子序列
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#"));
}

② 用C++求最長公共子序列問題

什麼意思，連續的還是求交集？

③ 求最長公共子序列的c語言代碼

？？？

④ 求數組的最大子數組值和最長公共子序列問題

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>。
最長公共子序列問題具有最優子結構性質。

⑤ 最長 公共子序列問題（演算法分析 C++）

#include <iostream>
#include <string>
using namespace std;
//主函數
int main()
{
int m,n;
char *x,*y;
int **b,**c;
void LCSLength(int m,int n,char *y,char *x,int **c,int **b);
void LCS(int i,int j,char *x,int**b);

cout<<"請輸入兩個序列的長度："<<endl;
cin>>m>>n;
x=new char[m];
y=new char[n];
cout<<"請輸入兩個序列："<<endl;
cin>>x>>y;
b=new int *[m + 1]; // 注意這里，原式沒有+1
for (int i=0;i<=m;i++)
b[i]=new int[n + 1]; // 注意這里，原式沒有+1
c=new int *[m + 1];
for (int j=0;j<=m;j++)
c[j]=new int[n + 1]; // 注意這里，原式沒有+1
LCSLength(m,n,x,y,c,b);
cout<<"最長公共子序列的元素個數為"<<c[m][n]<<endl;
cout<<"該序列為:";
LCS(m,n,x,b); //注意後面的內容是清理，暫時先跳過去，你先搞定主程序先
/* delete []x;
delete []y;
for(int k=0;k<=m;k++)
delete []b[k];
delete []b;
for(int h=0;h<=m;h++)
delete []c[h];
delete []c;
*/
return 0;
}
//計算最優值
void LCSLength(int m,int n,char *y,char *x,int **c,int **b)
{
int i,j;
for(i=1;i<=m;i++)c[i][0]=0;
for(j=0;j<=n;j++)c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i]==y[j]){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,char *x,int**b)
{
if(i==0||j==0)return;
if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i];}
else if(b[i][j]==2)LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}

⑥ （演算法 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;
}

⑦ 我想問一下在演算法設計（如圖）計算最長公共子序列中用動態規劃計算復雜度不也是(m*n)，如果我拿X中

如果要兩個字元串是不是有相同的字元，那麼是m*n，只是如果是子序列，每次掃描到相同的字元還要繼續往後掃描，這個是指數增長的

⑧ 最長公共子序列的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;
}

⑨ 求最長公共子序列的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

⑩ 最長公共子序列的空間時間優化演算法

樓主你好 這么專業的問題 只能 去問專業人 士 在這里 的不到答案的啊