最长公共子串算法

Question

我写了一个代码来查找两个字符串的LCS(最长的公共子串)。现在我想把它带到下一个层次，这意味着找到所有可用的LCS组合，但我不确定从哪里开始。下面是我的代码：

package MyPackage;

public class LCSAlgo {

    //finds the first col and first row of the matrix
    public static int[] [] LCSBase2(String a , String b){
        int [][] arr = new int[a.length()][b.length()];
        boolean flaga = false;
        boolean flagb = false;
        for(int i = 0 ; i<a.length();i++){
            if(a.charAt(i) == b.charAt(0) || flaga){
                flaga=true;
                arr[i][0] = 1;
            }
            else{
                arr[i][0] = 0;
            }
        }
        for(int j = 0 ; j<b.length();j++){
            if(b.charAt(j) == a.charAt(0) || flagb){
                flagb=true;
                arr[0][j] = 1;
            }
            else{
                arr[0][j] = 0;
            }

        }
        return arr;
    }
    //Fill the matrix with the substring combination
    public static int [][] LCSSol( String a , String b){
        int [][] arr2 = LCSBase2(a,b);
        for(int i = 1 ; i<a.length(); i++){
            for(int j = 1 ; j<b.length();j++){
                if(a.charAt(i) == b.charAt(j)){
                    arr2[i][j] = arr2[i-1][j-1]+1;
                }
                else{
                    if(arr2[i][j-1]>arr2[i-1][j]){
                        arr2[i][j] = arr2[i][j-1];
                    }
                    else
                        arr2[i][j] = arr2[i-1][j];
                }
            }
        }
        return arr2;
    }
    //prints the matrix
    public static void Print2D(int i , int j , int [][]arr){
        for(int a = 0;a<i;a++){
            System.out.println();
            for(int b = 0; b<j ; b++){
                System.out.print(arr[a][b]);
            }
        }
    }
    //returns one common substring of two Strings.
    public static String CommonSubstring( String a,String b ){
        int [] [] arr = LCSSol(a, b);
        int i = a.length()-1;
        int j = b.length()-1;
        String sub = "",subrev="";
        while(i>=0 && j>=0 && arr[i][j]>0){
            if(a.charAt(i) == b.charAt(j)){
                sub+=a.charAt(i);
                i--;
                j--;
            }
            else{
                if(arr[i][j-1]>arr[i-1][j]){
                    j--;
                }
                else{
                    i--;
                }
            }
        }
        for( i=sub.length()-1;i>=0;i--){
            subrev+=sub.charAt(i);
        }
        return subrev;
    }
    public static void main(String [] args){
        String s1 = "abcbdab";
        String s2 = "bdcaba";
        System.out.println(CommonSubstring(s1, s2));
    }
}

有人能指导我如何找到所有的组合吗？

Answer 1

你可以使用像Commons-collections这样的外部库。一旦这个库进入你的类路径，你就可以用CollectionsUtils轻松地改变所有的组合：

CollectionUtils.permutations(collection)