最长公共子序列代码

《最长公共子序列代码》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、packagesuanfa;importjava.io.*;importjava.util.ArrayList;importjava.util.List;publicclassLcs{publicstaticListre=newArrayList();staticintm,n;staticintc[][];staticcharb[][];publicLcs(){//构造方法Stringin;charx[],y[];BufferedReaderbuf=newBufferedReader(newInputStreamRe

2、ader(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();charb[][]=newchar[x.leng

3、th][y.length];intc[][]=newint[x.length][y.length];intlen=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);intsize=re.size();System.out.print("最长公共子序列为：");for(in

4、ti=0;i

5、tem.out.print(c[0][j]);}System.out.print("");for(inti=0;i<=m;i++){c[i][0]=0;b[i][0]='→';}for(inti=1;i<=m;i++){System.out.print(0);for(intj=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]='↘';}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]='↓';}else{c[i]

6、[j]=c[i][j-1];b[i][j]='→';}System.out.print(c[i][j]);}System.out.print("");}for(inti=0;i<=m;i++){for(intj=0;j<=n;j++){System.out.print(b[i][j]);}System.out.print("");}returnc[m][n];}//求公共子序列publicstaticvoidlcsPut(inti,intj,charx[],charb[][]){if(i==0

7、

8、j==0)return;if(b[

9、i][j]=='↘'){lcsPut(i-1,j-1,x,b);re.add(x[i]);}elseif(b[i][j]=='↓')lcsPut(i-1,j,x,b);elselcsPut(i,j-1,x,b);}//主方法publicstaticvoidmain(Stringargs[]){Lcslcs=newLcs();}}