最長公共子序列java

❶ 最長公共子序列的應用

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

❷ 最長公共子序列的代碼

publicclassLCSProblem{publicstaticvoidmain(String[]args){String[]x={,A,B,C,B,D,A,B};String[]y={,B,D,C,A,B,A};int[][]b=getLength(x,y);Display(b,x,x.length-1,y.length-1);}publicstaticint[][]getLength(String[]x,String[]y){int[][]b=newint[x.length][y.length];int[][]c=newint[x.length][y.length];for(inti=1;i<x.length;i++){for(intj=1;j<y.length;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=0;}else{c[i][j]=c[i][j-1];b[i][j]=-1;}}}returnb;}publicstaticvoidDisplay(int[][]b,String[]x,inti,intj){if(i==0||j==0)return;if(b[i][j]==1){Display(b,x,i-1,j-1);System.out.print(x[i]+);}elseif(b[i][j]==0){Display(b,x,i-1,j);}elseif(b[i][j]==-1){Display(b,x,i,j-1);}}}

❸ 關於用動態規劃法求最大公共子序列的問題

#include <iostream>
#include <string>
using namespace std;
#define N 100 // 宏定義N的初始值為100
char a[N], b[N], str[N]; //a用於保存第一個輸入的字元的，b用於保存第二個，str用於判斷兩個字元是不是都遍歷到了'\0'(到了的話說明字元串處理完畢)，先初始化為N
int c[N][N]; //int型數組，初始化為N，用於保存兩個字元串的內容
//下面你要跟著程序的調用規律走，先看主函數調用的是build_lcs(),然後是lcs_len()
int lcs_len(char* a, char* b,int c[][N]) //用於計算兩個字元串的每個元素的內容！
{
int m=strlen(a), n=strlen(b), i, j; //聲明m，n，i,j變數,其中的strlen()函數是用來獲取字元串長度的
for (i=0; i<=m; i++) //
c[i][0]=0; //遍歷第一個字元串的內容，分別保存到c的一維數組中
for (i=0; i<=n; i++) //
c[0][i]=0; //遍歷第二個字元串的內容，分別保存到c的二維數組中
for (i=1; i<=m; i++) //第一層FOR循環
{ //
for (j=1; j<=n; j++) //第二層FOR循環
{ //
//
if (a[i-1]==b[j-1]) //判斷第一個字元串的第i(-1是為了去掉'\0')個元素的值等於第二個字元串第j個元素
c[i][j]=c[i-1][j-1]+1; //
else if (c[i-1][j]>=c[i][j-1]) //如果不是，則判斷第一個字元數組的第i個元素與第二個字元數組所有元素相等(j循環j遍,i才循環1遍)
c[i][j]=c[i-1][j]; //
else //如果不是，則判斷第一個字元數組的第j個元素與第二個字元數組所有元素相等(i循環j遍,j才循環1遍)
c[i][j]=c[i][j-1]; //
} //
} //
return c[m][n]; //得到相同的元素並返回
}
char* build_lcs(char s[],char* a,char* b)
{
int i=strlen(a), j=strlen(b);
int k=lcs_len(a,b,c);
s[k]='\0';
while (k>0) //下面都很簡單了！
{
if (c[i][j]==c[i-1][j])
i--;
else if (c[i][j]==c[i][j-1])
j--;
else
{
s[--k]=a[i-1];
i--; j--;
}
}
cout<<s<<endl;
return s;
}
void main()
{
cout<<"輸入兩個長度小於"<<N<<"的字元串"<<endl;
cin>>a;
cin>>b;
cout<<"LCS="<<build_lcs(str,a,b)<<endl;
}

❹ 求兩個字元串的最長公共子串，要求輸入兩個字元串，輸出他們的最長公共子串，包括長度。

遍歷一下就好了，java代碼：
public class CommonSubString {

public String search(String s1,String s2)
{
String max = "";
for(int i=0; i<s1.length(); i++)
{
for(int j=i; j<s1.length(); j++)
{
String sub = s1.substring(i,j);
if((s2.indexOf(sub)!=-1)&&sub.length()>max.length())
{
max = sub;
}
}
}
return max;
}

public static void main(String[] args)
{
String s1 = "abcdefghigj";
String s2 = "xyzabcdefigj";
String output = new CommonSubString().search(s1,s2);
System.out.println(output);
}
}

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

❻ 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));
}
}

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

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