最长的公共子串算法

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。一旦这个库是你的classpath里面，你可以用CollectionsUtils容易置换的所有组合：

CollectionUtils.permutations(collection)