java 动态规划算法求解最长公共子串

浏览数：33 / 时间：2015年06月08日

最近在项目中碰到了这样的一个问题，要比较JS和CSS是否做了修改，先是想着借助第三方工具发现没找到，后面转念一想，这个问题不就是对两个文件的第一行求最大的公共子串嘛，既然是要求公共子串的最大长度，由此想到了动态规划算法。

代码是从网上C++改写过来的，感谢那位C++的兄弟，代码如下：

package dp;

/**
 * 用动态规划算法求解  最长公共子串
 * @author 
 *
 */
public class LCSSuffix {

    private static String getLCSLength(String s,String t){
        int p = s.length() ;
        int q = t.length();
        
        String[][] num = new String[p][q];
        char char1 = ‘\0‘;
        char char2 = ‘\0‘ ;
        
        int len = 0 ;
        String lcs = "";
        for(int i = 0;i<p ;i++){
            for(int j=0;j<q;j++){
                char1 = s.charAt(i);
                char2 = t.charAt(j);
                if(char1 != char2){
                    num[i][j] = "";
                }else {
                    if(i==0 ) num[i][j] = String.valueOf(char1) ;
                    else if(j ==0)num[i][j] = String.valueOf(char2);
                    else num[i][j] = num[i-1][j-1] +String.valueOf(char1) ;
                    
                    if(num[i][j].length() > len){
                        len = num[i][j].length();
                        lcs = num[i][j];
                    }else if(num[i][j].length() == len){
                        lcs = lcs +","+num[i][j] ;
                    }
                }
            }
        }
        return lcs ;
    }
    
    public static void main(String[] args) {
        String lcs = getLCSLength("baba","abab");
        System.out.println(lcs);
    }
}