fac3_3.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 73 页，例
//最长公共子序列动态规划解法
public class Fac3_3{
   public static int lcsLength(char []x,char []y,int [][]b)
   {
     int m=x.length-1;
     int n=y.length-1;
     int [][]c=new int[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]==y[j]){
           c[i][j]=c[i-1][j-1]+1;
           b[i][j]=1;
           }
          else
           if(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;
           }
         }
        return c[m][n];
    }

  public static void lcs(int i,int j,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]);
      }
    else if (b[i][j]==2)lcs(i-1,j,x,b);
         else  lcs(i,j-1,x,b);
  }

  public static void main(String args[])
  {
    //为保障统计正确，需在输入字符数组a和b的第一个字符设置标示，该字符不参与统计
    char []a={'@','t','h','i','s','c','b','o','o','k'};
    char []b={'#','t','i','s','n','o','o','k'};  
    int m=a.length-1;
    int n=b.length-1;
    int [][]q=new int[m+1][n+1];
    System.out.println("最大字符串字符个数="+lcsLength(a,b,q));
    lcs(m,n,a,q);
  }
}