java最長公共子序列

1. 幫我講下題目要求的是什麼... （要求解什麼）

序列的子序列是將所給序列略去幾個元素或者一個不略。給出一個序列X = <x1, x2, ..., xm>，另一個序列 Z = <z1, z2, ..., zk>是X的子序列 如果存在一個序列X的指數的嚴格遞增的子序列<i1, i2, ..., ik> 即對於所有的j = 1,2,...,k, xij = zj。例如，Z = <a, b, f, c>是含指數序列<1, 2, 4, 6>的 X = <a, b, c, f, b, c>的子序列。現給出兩個序列X和Y，要求找出X和Y最大長度公共子集。
輸入數據來自文本文件。文件中的每個數據都由兩個字元串組成來表明所給序列。各個序列由空格隔開。輸入數據是正確的。對於每個數據的格式，要求在標准輸出埠隔行輸出公共子序列的最大長度。
例子輸入：
abcfbc abfcab
programming contest
abcd mnp
例子輸出：
4
2
0
——————————————————————————————————————
就是要編程找出公共子集的最大長度。。。 賞點分吧。。。 沒分從文庫下小說了~~~

2. 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#"));}

3. java求最大公共子串

二樓改的
c = b.substring(i,j-1);
之後下標越界沒了。

程序無法出結果，中間有死循環。當while語句執行完之後j是a.length();然後是執行內循環for語句for(j=b.length()-1;j>0;j--) 此時只比較J>0;。。。。好像是個死循環。最內層的循環可以在加一個int k來控制。多次運行導致cpu上升至100%的。

提供一種矩陣演算法，這是LCS的一種演算法：
public class stringCompare {

/**求最長匹配子字元串演算法
str數組記錄每行生成的最大值strmax
max數組記錄str數組最大時所處的列號nummaxj
最大子字元串為substring(nummax-strmax+1,strmax+1)
*/

public static void main(String[] args) {
String s1="asdfgxxcvasdfgc";
String s2="asdfxxcv";
int m=s1.length();
int n=s2.length();
int k=0;
int nummax=0;
int []str=new int[m];
int []max=new int[m];
int []num=new int[m];

for(int i=0;i<m;i++) //生成矩陣數組
for(int j=n-1;j>=0;j--)
{
if(s1.charAt(i)==s2.charAt(j))

if(i==0||j==0)
{
num[j]=1;
max[i]=j;
str[i]=1;
}
else
{
num[j]=num[j-1]+1;
if(max[i]<num[j])
{
max[i]=j;
str[i]=num[j];
}
}
else
num[j]=0;
}

for(k=0;k<m;k++) //求str數組的最大值
{
if(nummax<str[k])
{
nummax=str[k];
}
}

for(k=0;k<m;k++)
if(nummax==str[k])
System.out.println(s2.substring(max[k]-str[k]+1,max[k]+1));
}
}

4. 最長公共子串和最長公共子序列的區別。舉個例子不要寫代碼。

應該是這樣：
字元串1：abcde
字元串2：abcdfe
那麼：
最長公共子串：abcd
最長公共子序列：abcde
就是公共子串，必須在待匹配字元串中連續，而公共子序列只需要相對順序匹配就行。
前者一般用KMP演算法，後者一般用動態規劃解決吧。

5. 最長公共子序列的應用

最長公共子序列是一個十分實用的問題，它可以描述兩段文字之間的「相似度」，即它們的雷同程度，從而能夠用來辨別抄襲。對一段文字進行修改之後，計算改動前後文字的最長公共子序列，將除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分准確。簡而言之，網路知道、網路都用得上。

6. 動態規劃求最長公共子序列怎麼得到路徑

最長公共子串問題：一個給定序列的子序列是在該序列中刪去若干元素後得到的序列。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。最長公共子串就是求給定兩個序列的一個最長公共子序列。

7. 求最長公共子序列（動態規劃）

// 求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);
}