最長(zhǎng)公共子序列java源程序代碼

以下為最長(zhǎng)公共子序列問(wèn)題的兩種程序，分別通過(guò)兩種算法實(shí)現(xiàn)：方法一：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("最長(zhǎng)公共子序列："); intn=lcsLength(x,y,b); System.out.println(); System.out.println("其長(zhǎng)度為："+n); }}方法二：packagecn.lgh;importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.ArrayList;importjava.util.List;/***動(dòng)態(tài)規(guī)劃法解最長(zhǎng)公共子系列。*@author藍(lán)冠恒*/publicclassLCS{ publicstaticList<Character>resultList=newArrayList<Character>(); /** *計(jì)算最優(yōu)值 *@paramx *字符系列數(shù)組 *@paramy *字符系列數(shù)組 *@paramc *存儲(chǔ)x和y最長(zhǎng)公共子系列長(zhǎng)度數(shù)組 *@paramb *記錄c中元素對(duì)應(yīng)子問(wèn)題的解的數(shù)組 */ 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; } } } } /** *構(gòu)造最長(zhǎng)公共子系列 *@parami *數(shù)組下標(biāo) *@paramj *數(shù)組下標(biāo) *@paramx *字符系列數(shù)組 *@paramb *記錄c中元素對(duì)應(yīng)子問(wèn)題的解的數(shù)組 */ 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("請(qǐng)輸入第一串字符系列(按數(shù)字鍵1退出系統(tǒng))："); input=in.readLine().trim(); }while(input.equals("")); if(input.equals("1")){ break; } input="S"+input; x=input.toCharArray(); do{ System.out.println("請(qǐng)輸入第二串字符系列(按數(shù)字鍵1退出系統(tǒng))："); 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);//計(jì)算最優(yōu)值 lcs(x.length-1,y.length-1,x,b);//構(gòu)造最長(zhǎng)公共子系列 intsize=resultList.size(); System.out.print("解得最長(zhǎng)公共子系列為："); for(i