最长公共子序列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);
}