最长公共子序列（java实现）

package 最长公共子序列; public class LCS { public static void main(String[] args) { //↖←↑ String [] X={"A","B","C","B","D","A","B"}; String [] Y={"B","D","C","A","B","A"}; LCS(X,Y,X.length,Y.length); } public static void LCS(String []X,String []Y,int m,int n) { int[][]C=new int [m+1][n+1]; String[][]B=new String [m+1][n+1]; for(int i=0;i<=m;i++) { C[i][0]=0; } for(int i=0;i<=n;i++) { C[0][i]=0; } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(X[i-1]==Y[j-1]){ 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]="←"; } } } //测试 for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { System.out.print(C[i][j]+""+"B["+i+"]["+j+"]="+B[i][j]+"\t"); } System.out.println(); } StructureSequence(B,X,m,n); } public static void StructureSequence(String [][]B,String[] X,int i,int j){ if(i==0||j==0){ return; } if(B[i][j]=="↖"){ System.out.println(X[i-1]); StructureSequence(B,X,i-1,j-1); } else if(B[i][j]=="↑"){ StructureSequence(B,X,i-1,j); } else{ StructureSequence(B,X,i,j-1); } } }