最长公共子序列java源程序代码

以下为最长公共子序列问题的两种程序，分别通过两种算法实现：方法一：publicclassLcsLength{ publicstaticintlcsLength(char[]x,char[]y,int[][]b) { intm=x.length; intn=y.length; int[][]c=newint[m+1][n+1]; for(inti=0;i<=m;i++)c[i][0]=0; for(inti=0;i<=n;i++)c[0][i]=0; for(inti=1;i<=m;i++) for(intj=1;j<=n;j++) { if(x[i-1]==y[j-1]) { 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; } } inti=m;intj=n; lcs(i,j,x,b); returnc[m][n]; } publicstaticvoidlcs(inti,intj,char[]x,int[][]b) { if(i==0||j==0)return; if(b[i][j]==1) { lcs(i-1,j-1,x,b); System.out.print(x[i-1]+","); } elseif(b[i][j]==2)lcs(i-1,j,x,b); elselcs(i,j-1,x,b); } publicstaticvoidmain(Stringargs[]) { char[]x={'a','b','c','b','d','a','b'}; char[]y={'b','d','c','a','b','a'}; int[][]b=newint[x.length+1][y.length+1]; System.out.print("最长公共子序列："); intn=lcsLength(x,y,b); System.out.println(); System.out.println("其长度为："+n); }}方法二：packagecn.lgh;importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.ArrayList;importjava.util.List;/***动态规划法解最长公共子系列。*@author蓝冠恒*/publicclassLCS{ publicstaticList<Character>resultList=newArrayList<Character>(); /** *计算最优值 *@paramx *字符系列数组 *@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<=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; } } } } /** *构造最长公共子系列 *@parami *数组下标 *@paramj *数组下标 *@paramx *字符系列数组 *@paramb *记录c中元素对应子问题的解的数组 */ publicstaticvoidlcs(inti,intj,charx[],int[][]b){ if(i==0||j==0){ return; } if(b[i][j]==1){ lcs(i-1,j-1,x,b); resultList.add(x[i]); }elseif(b[i][j]==2){ lcs(i-1,j,x,b); }else{ lcs(i,j-1,x,b); } } publicstaticvoidmain(Stringarg[]){ Stringinput; char[]x; char[]y; BufferedReaderin=newBufferedReader(newInputStreamReader(System.in)); do{ try{ do{ System.out.println("请输入第一串字符系列(按数字键1退出系统)："); input=in.readLine().trim(); }while(input.equals("")); if(input.equals("1")){ break; } input="S"+input; x=input.toCharArray(); do{ System.out.println("请输入第二串字符系列(按数字键1退出系统)："); input=in.readLine().trim(); }while(input.equals("")); if(input.equals("1")){ break; } 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);//计算最优值 lcs(x.length-1,y.length-1,x,b);//构造最长公共子系列 intsize=resultList.size(); System.out.print("解得最长公共子系列为："); for(i