editdis.java

自己编写的几个动态规划算法的例子

/*
 * 求两个字符串的编辑距离（EditDis.java） By JoyChou   Created on 2006年4月20日, 下午12:54
 * 根据课本中的求最长公共子序列的算法，确定公子自序列在各自串中的位置，然后求出
 * 两个字符串间的编辑距离
 * 例如：串 A="abfc" 和B= "bekcd"，显然它们的公共子序列为 " bc ",将 A,B 分别用
 * 'b'和'c'划分成 a (b) f (c) 和  (b) e k (c) d，如果想要使得A转换成B，
 * 则只要 先删除 'a',然后删除'e',将'f'变成'k',最后删除'd'，即可。
 * 因此它们的编辑距离应该为 d(A,B) = 1+2+1  
 */
package editdistance;
import java.lang.*;
import java.io.*;

public class EditDis {
    
    //计算串x,y从第二个字母开始的最大公共子串
    public static int lcsLength(String x,String y,int[][] b){
        int i,j;
        int m=x.length()-1;
        int n=y.length()-1;
        int[][]c=new int[m+1][n+1];
        //initialization
        c[0][0] = 0;
        for( i=1;i<=m; i++)    c[i][0] = 0;
        for( i=1 ; i<= n; i++)  c[0][i] = 0;
        for( i = 1; i<=m ; i++)
            for( j=1; j<= n; j++){
            if( x.charAt(i) == y.charAt(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 main(String[] args) throws IOException{
        // TODO code application logic here
     
        BufferedReader myIn =new BufferedReader(new InputStreamReader(System.in));
        
        System.out.print("Please input the first string A : ");
        String A = myIn.readLine();
        System.out.println(A);
        System.out.print("Please input the second strin B : ");
        String B = myIn.readLine();
        System.out.println(B);
    
       System.out.print("The EditingDistance between \""+A+"\" and \""+B+ "\" : d (A ,B) = ");   
        
        A = "s".concat(A);
        B = "s".concat(B);
            
        int m=A.length()-1;
        int n=B.length()-1;
        int b[][]=new int[m+1][n+1];
        lcsLength(A, B, b);
       
        int ED=0; //the editing distance
        int tempI=m+1;
        int tempJ=n+1;
        int i,j;
        b[0][0]=1;
        for(i=1;i<=m;i++)  b[i][0] = 2;
        for( i=1;i<=n ;i++) b[0][i] =3;
        i=m;
        j=n;
        //根据最长公共子序列的位置来计算两个字符串的编辑距离
        while( (i>=0) && (j>=0)){       
           if( b[i][j] == 1 ){
              ED+=Math.max(tempI-i-1,tempJ-j-1);
              tempI=i;
              tempJ=j;   
              i--;
              j--;
             }
           else if( b[i][j] == 2 )
               i--;
           else j--;              
        }
        System.out.println(ED);
        return;   
    }
}