两个字符串的所有可能的LCS（最长公共子序列）

Question

我们可以通过DP（动态规划）找到两个字符串的LCS（最长公共子序列）。通过跟踪DP表，我们可以得到LCS。但是如果存在多于一个LCS，我们如何才能获得所有这些？

实施例：

string1 : bcab 
string2 : abc 

这里既有 “AB” 和 “BC” 是LCS。

Answer 1

当您计算DP表中的单元格时，请保留一个指向用于该结果的前一个单元格的反向指针。如果存在平局，则为所有并列结果保留多个后向指标。然后沿着所有路径使用后向回车追溯路径。

Answer 2

这是一个可用的java解决方案。为了解释你可以看到我的回答 How to print all possible solutions for Longest Common subsequence

static int arr[][]; 
static void lcs(String s1, String s2) { 
    for (int i = 1; i <= s1.length(); i++) { 
     for (int j = 1; j <= s2.length(); j++) { 
      if (s1.charAt(i - 1) == s2.charAt(j - 1)) 
       arr[i][j] = arr[i - 1][j - 1] + 1; 
      else 
       arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]); 
     } 
    } 
} 

static Set<String> lcs(String s1, String s2, int len1, int len2) { 
    if (len1 == 0 || len2 == 0) { 
     Set<String> set = new HashSet<String>(); 
     set.add(""); 
     return set; 
    } 
    if (s1.charAt(len1 - 1) == s2.charAt(len2 - 1)) { 
     Set<String> set = lcs(s1, s2, len1 - 1, len2 - 1); 
     Set<String> set1 = new HashSet<>(); 
     for (String temp : set) { 
      temp = temp + s1.charAt(len1 - 1); 
      set1.add(temp); 
     } 
     return set1; 
    } else { 
     Set<String> set = new HashSet<>(); 
     Set<String> set1 = new HashSet<>(); 
     if (arr[len1 - 1][len2] >= arr[len1][len2 - 1]) { 
      set = lcs(s1, s2, len1 - 1, len2); 
     } 
     if (arr[len1][len2 - 1] >= arr[len1 - 1][len2]) { 
      set1 = lcs(s1, s2, len1, len2 - 1); 
     } 
     for (String temp : set) { 
      set1.add(temp); 
     } 
     //System.out.println("In lcs" + set1); 
     return set1; 

    } 
} 


public static void main(String[] args) { 
    String s1 = "bcab"; 
    String s2 = "abc"; 
    arr = new int[s1.length() + 1][s2.length() + 1]; 
    lcs(s1, s2); 
    System.out.println(lcs(s1, s2, s1.length(), s2.length())); 
} 

Answer 3

这里是一个注释Java程序找出所有可能的LCS。

import java.util.HashSet; 
import java.util.Scanner; 
import java.util.Set; 

public class LongestCommonSubsequence { 

    public static int[][] LCSmatrix(String X, String Y) { 
     //we ignore the top most row and left most column in this matrix 
     //so we add 1 and create a matrix with appropriate row and column size 
     int m = X.length() + 1, n = Y.length() + 1; 

     int[][] c = new int[m][n]; 

     for (int i = 1; i < m; i++) { 
      for (int j = 1; j < n; j++) { 
       //since we added 1 to row size and column size, 
       // we substract 1 from i,j to find the char at that index 
       if (X.charAt(i - 1) == Y.charAt(j - 1)) { 
        c[i][j] = c[i - 1][j - 1] + 1; 
       } else if (c[i - 1][j] >= c[i][j - 1]) { 
        c[i][j] = c[i - 1][j]; 
       } else { 
        c[i][j] = c[i][j - 1]; 
       } 
      } 
     } 
     printMatrix(c); 
     return c; 
    } 

    public static void printMatrix(int[][] grid) { 
     for (int r = 0; r < grid.length; r++) { 
      for (int c = 0; c < grid[r].length; c++) { 
       System.out.print(grid[r][c] + " "); 
      } 
      System.out.println(); 
     } 
    } 

    public static void allLCS(int[][] c, String X, String Y, int i, int j, Set<String> setLCS, String s) { 
     //return when either of the string length is 0 
     if (i == 0 || j == 0) { 
      setLCS.add(s); 
      return; 
     } 

     //if last characters are equal, they belong in lcs 
     if (X.charAt(i - 1) == Y.charAt(j - 1)) { 
      //prepend the char to lcs since, we are going backwards 
      s = X.charAt(i - 1) + s; 
      //continue finding lcs in substrings X.substring(0,i-1) and Y.substring(0,j-1) 
      allLCS(c, X, Y, i - 1, j - 1, setLCS, s); 
     } // if there is a tie in matrix cells, we backtrack in both ways, 
     // else one way, which ever is greater 
     else if (c[i - 1][j] == c[i][j - 1]) { 
      //continue finding lcs in substring X.substring(0,i-1) 
      allLCS(c, X, Y, i - 1, j, setLCS, s); 
      //continue finding lcs in substring Y.substring(0,j-1) 
      allLCS(c, X, Y, i, j - 1, setLCS, s); 
     } else if (c[i - 1][j] > c[i][j - 1]) { 
      allLCS(c, X, Y, i - 1, j, setLCS, s); 
     } else { 
      allLCS(c, X, Y, i, j - 1, setLCS, s); 
     } 

    } 

    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 

     System.out.println(" Enter String X and Y : "); 

     String X = sc.next(); 
     String Y = sc.next(); 

     sc.close(); 

     Set<String> set = new HashSet<String>(); 
     allLCS(LCSmatrix(X, Y), X, Y, X.length(), Y.length(), set, ""); 

     System.out.println(set.toString()); 
    } 

}