最长公共子序列算法问题JAVA源代码免费下

《最长公共子序列算法问题JAVA源代码免费下》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.ArrayList;importjava.util.Scanner;importjava.util.List;/***动态规划法解最长公共子系列。*@author蓝冠恒*/publicclassLCS{publicstaticListresultList=newArrayList();/***计算最优值*@paramx

2、*字符系列数组*@paramy*字符系列数组*@paramc*存储x和y最长公共子系列长度数组*@paramb*记录c中元素对应子问题的解的数组*/publicstaticvoidlcsLength(charx[],chary[],int[][]c,int[][]b){intm=x.length-1;intn=y.length-1;resultList.clear();for(inti=1;i<=m;i++){c[i][0]=0;}for(inti=1;i<=n;i++){c[0][i]=0;}for(inti=1;i<=m;i++){for(intj=1;j<=

3、n;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]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}}publicstaticvoidlcs(inti,intj,charx[],int[][]b){if(i==0

4、

5、j==0){return;}if(b[i][j]==1){lcs(i-1,j-1,x,b);resultList.add(x[i]);}elseif(b[i

6、][j]==2){lcs(i-1,j,x,b);}else{lcs(i,j-1,x,b);}}publicstaticvoidmain(Stringarg[]){Stringa;Stringinput;char[]x;char[]y;Scannerscan=newScanner(System.in);BufferedReaderin=newBufferedReader(newInputStreamReader(System.in));do{try{do{System.out.println("请输入第一串字符系列");input=in.readLine().tri

7、m();}while(input.equals(""));input="S"+input;x=input.toCharArray();do{System.out.println("请输入第二串字符系列");input=in.readLine().trim();}while(input.equals(""));input="S"+input;y=input.toCharArray();int[][]b=newint[x.length][y.length];int[][]c=newint[x.length][y.length];lcsLength(x,y,c,b);/

8、/计算最优值lcs(x.length-1,y.length-1,x,b);//构造最长公共子系列intsize=resultList.size();System.out.print("最长公共子系列为:");for(inti=0;i

9、);}while(a.equals("y"));}}