当前位置：首页>工作总结>最长公共子序列代码

最长公共子序列代码

时间：23-11-23 网友

package suanfa;

import java.io.*;

import java.util.ArrayList;

import java.util.List;

public class Lcs {

public static List re=new ArrayList();

static int m,n;

static int c[][];

static char b[][];

public Lcs(){//构造方法

String in;

char x[],y[];

BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));

do{

try{

do{

System.out.println("请输入第一个字符串：");

in=buf.readLine().trim();

}while(in.equals(""));

in="S"+in;

x=in.toCharArray();

do{

System.out.println("请输入第二个字符串：");

in=buf.readLine().trim();

}while(in.equals(""));

in="S"+in;

y=in.toCharArray();

char b[][]=new char[x.length][y.length];

int c[][]=new int[x.length][y.length];

int len=lcsLength(x,y,b,c);//计算最长公共子序列的长度

System.out.println("最长公共子序列的长度为:"+len);

if(len==0){System.out.println("没有公共子序列!");return;}

else{

lcsPut(x.length-1,y.length-1,x,b);

int size=re.size();

System.out.print("最长公共子序列为：");

for(int i=0;i

System.out.print(re.get(i));

}

System.out.print("\n");}

}catch(IOException e){

e.printStackTrace();

}

}while(true);

}

//求长度的方法

public int lcsLength(char x[],char y[],char b[][],int c[][]){

m=x.length-1;

n=y.length-1;

re.clear();for(int j=0;j<=n;j++) {c[0][j]=0;b[0][j]='→';System.out.print(c[0][j]);}System.out.print("\n");

for(int i=0;i<=m;i++) {c[i][0]=0;b[i][0]='→';}

for(int i=1;i<=m;i++){

System.out.print(0);

for( int j=1;j<=n;j++){

if (x[i]==y[j]){

c[i][j]=c[i-1][j-1]+1;

b[i][j]='↘';

}

else if (c[i-1][j]>=c[i][j-1]){

c[i][j]=c[i-1][j];

b[i][j]='↓';

}

else{

c[i][j]=c[i][j-1];

b[i][j]='→';

}

System.out.print(c[i][j]);

}System.out.print("\n");

}

for(int i=0;i<=m;i++){

for(int j=0;j<=n;j++){

System.out.print(b[i][j]);

}

System.out.print("\n");

}

return c[m][n];

}

//求公共子序列

public static void lcsPut(int i,int j,char x[],char b[][]){

if (i==0 || j==0)

return;

if (b[i][j]=='↘'){

lcsPut(i-1,j-1,x,b);

re.add(x[i]);

}

else if(b[i][j]=='↓') lcsPut(i-1,j,x,b);

else lcsPut(i,j-1,x,b);

}

//主方法

public static void main(String args[]){

Lcs lcs=new Lcs();

}

《最长公共子序列代码》相关文档：

序列的最长公共子序列算法06-23

最长公共上升子序列(LCIS)的平方算法06-23

最长公共子序列代码

最新文档