题目

Description
给定两个字符串，返回两个字符串的最长公共子序列（不是最长公共子字符串），可能是多个。

Input
输入第一行为用例个数，每个测试用例输入为两行，一行一个字符串

Output
如果没有公共子序列，不输出，如果有多个则分为多行，按字典序排序。

示例：
输入：
1
1A2BD3G4H56JK
23EFG4I5J6K7

输出：
23G456K
23G45JK

分析

分析一

最长公共子序列（Longest Common Subsequence）和最长公共子字符串（Lonest Common Substring）是不相同的。子序列并不要求在原字符串中是连续的，只需要保持相对顺序即可，但子串要求在原字符串中是连续的。

分析二

a) 我们设字符串A[0,m]，字符串B[0,N]，我们从左到右分别同时对A、B字符串用双指针进行遍历，可以发现A[0,i]和B[0,j]的最长子序列与A[0,i-1]和B[0,j-1]的最长子序列是有关系的。

b) 假设我们现在A串处于位置i-1，B串处于位置j-1，记此时A[0,i-1]和B[0,j-1]的最长公共子序列长度为L，那么有如下两种情况：

如果A[i] = B[j]，那么A[0,i]和B[0,j]的最长子序列的长度就是A[0,i-1]和B[0,j-1]的最长子序列再加1，即L+1
若A[i]！=B[j]，那么A[0,i]和B[0,j]的最长公共子序列，要么就是i往后走一步，j不动；要么就是i不动，j往后走一步，二者取最大值。即为max(公共子串长度[i,j-1],公共子串长度[i-1,j])。

c) 因此，我们可以采用递归的方式进行解决。下面可以给出伪代码：

int longestCommonSubsequence(char str1[], int len1, char str2[], int len2) {
    if (len1 == 0 || len2 == 0) {
        return 0;
    } else if (str1[len1-1] == str2[len2-1]) {
        return lcs(str1, len1-1, str2, len2-1) + 1;
    } else {
        int lcs1 = lcs(str1, len1-1, str2, len2);
        int lcs2 = lcs(str1, len1, str2, len2-1);
        return max(lcs1, lcs2);
    }
}

d) 然而，递归的问题就是有太多重复计算了，性能比较慢。并且，这个递归只能给出长度，又该怎么输出子串呢？

e) 既然可以用递归，我们就可以尝试将这个问题划分为子问题，采用动态规划的思想，进行解决。既然尝试使用动态规划，那么问题的关键就是定义数组元素的含义，同时找到递推公式，也就是数组元素之间的关系。

f) 设数组LCS[i,j]表示字符串A[0,i]和字符串B[0,j]的最长公共子序列的长度，则我们有：

LCS[i,j] = 0 (如果i=0 或者 j=0)
LCS[i,j] = LCS[i-1,j-1] + 1 (如果i,j>0 且 A[i] = B[j])

LCS[i,j] = max(LCS[i-1,j], LCS[i,j-1]) （如果i,j>0 且 A[i] != B[j]）
我们可以发现这个问题具有最优子结构以及重叠子问题的特征，因此可以使用动态规划来解决。

// 计算最长公共子序列长度
int longestCommonSubsequence(String stringA, String stringB) {
    int lenOfStrA = stringA.length();
    int lenOfStrB = stringB.length();
    int[][] table = new int[lenOfStrA + 1][lenOfStrB + 1];
    for (int i = 0; i < lenOfStrA + 1; i++) {
        for( int j = 0; j < lenOfStrB + 1; j++) {
            if (i == 0 || j == 0) {
                table[i][j] = 0;
            } else if (stringA.charAt(i-1) == stringB.charAt(j-1)) {
                table[i][j] = table[i-1][j-1] + 1;
            } else {
                table[i][j] = Math.max(table[i-1][j], table[i][j-1]);
            }
        }
    }
    return table[lenOfStrA][lenOfStrB];
}

分析三

通过上面的分析，我们可以知道了如何计算最长公共子序列的长度。下面要解决的问题就是如何找出这些最长公共子序列的内容。
在上面的代码中，我们构建了一个二维数组，这个数组的含义是：table[i][j]表示A[0,i]和B[0,j]的最长公共子序列的长度。
由上面的分析我们知道，table[i][j]的值可能有两种来源（除去初始化的0）：

当A[i]=B[j]时，table[i][j] = table[i-1][j-1]+1，相当于在这个二维表中从左上角跳到右下角
当A[i]!=B[j]时，table[i][j] = max(table[i][j-1], table[i-1][j])，相当于从table[i-1][j-1]的位置，判断下方（table[i][j-1]）的值大还是右方（table[i-1][j]）的值大，谁的值大就走哪边。
因此，我们可以通过这个二维表，从最右下角的位置进行回溯，往回遍历，从而获得这些公共子序列。

首先看只输出一个最长公共子序列的情况，算法如下：

如果str1[m] = str2[n]，那么str1[m]（也就是str2[j]）肯定被包含在最后的输出最长子序列串内，把str1[m]存入缓存currentLCS，并把m-1,n-1。
如果str1[m] ≠ str2[n]，那么我们继续比较两个值：table[m-1][n]和table[m][n-1]的值：
- table[m-1][n] > table[m][n-1] 就选table[m-1][n]分支，表明它最长。
- table[m-1][n] < table[m][n-1] 就选table[m][n-1]分支，表明它最长。
- table[m-1][n] = table[m][n-1] 随便选一个，table[m-1][n]或者table[m][n-1]，因为他们结果是一样的长度。其实相等的含义表明这样的子序列串可能会包含多条，此时只要求输出一个最长公共子串，则可任选一条，如选择横向优先，即str1优先。

直到m=0或者n=0，倒序输出缓存currentLCS即可。

void findLCS(String strA, String strB, int[][] table)
{
    String currentLCS = "";
    int i = strA.length();
    int j = strB.length();
    while (i > 0 && j > 0)
    {
        if (strA.charAt(i - 1) == strB.charAt(j - 1))
        {
            currentLCS += strA.charAt(i - 1);
            i--;
            j--;
        }
        else if (table[i - 1][j] > table[i][j - 1])
        {           
            i--;    
        }   
        else
        {  // table[i - 1][j] <= table[i][j - 1]
            j--;
        }                   
    }
    System.out.println((reverseString(currentLCS)));
}

分析四

在分析三中讨论了只需要输出其中一个最长公共子序列的情况，现在讨论需要输出所有最长公共子序列的情况。
通过上面的分析，我们知道在当table[m-1][n] = table[m][n-1]时，代表的意义是此时存在了多个公共子序列，说明最长公共子序列有多个，因此左边、上方两个方向都要进行回溯，这里用到了递归。

void findAllLCS(String strA, String strB, int i, int j, int[][] table, String currentLCS,
        Set<String> allLCSResultSet)
{
    while (i > 0 && j > 0)
    {
        if (strA.charAt(i - 1) == strB.charAt(j - 1))
        {
            currentLCS += strA.charAt(i - 1);
            i--;
            j--;
        }
        else
        {
            if (table[i - 1][j] > table[i][j - 1])
            {
                i--;
            }
            else if (table[i - 1][j] < table[i][j - 1])
            {
                j--;
            }
            else
            {
                findAllLCS(strA, strB, i - 1, j, table, currentLCS, allLCSResultSet);
                findAllLCS(strA, strB, i, j - 1, table, currentLCS, allLCSResultSet);
                return;
            }
        }
    }
    // 最后结果存储在allLCSResultSet中
    allLCSResultSet.add(reverseString(currentLCS));
}

完整代码

class Pair<K, V>
{
    private K key;

    private V value;

    public Pair(K key, V value)
    {
        this.key = key;
        this.value = value;
    }

    public K getKey()
    {
        return key;
    }

    public V getValue()
    {
        return value;
    }
}

public class Main
{

    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int numOfTestCases = scanner.nextInt();
        while (numOfTestCases-- > 0)
        {
            String strA = scanner.next();
            String strB = scanner.next();
            Pair<Integer, int[][]> result = calLengthOfLCS(strA, strB);
            int[][] table = result.getValue();

            // 默认按字典序排序
            Set<String> resultSet = new TreeSet<>();

            findAllLCS(strA, strB, strA.length(), strB.length(), table, "", resultSet);
            resultSet.forEach(System.out::println);
        }
    }

    private static Pair<Integer, int[][]> calLengthOfLCS(String strA, String strB)
    {
        int lengthOfStrA = strA.length();
        int lengthOfStrB = strB.length();
        if (lengthOfStrA == 0 || lengthOfStrB == 0)
        {
            return new Pair<>(0, new int[0][0]);
        }
        int[][] table = new int[lengthOfStrA + 1][lengthOfStrB + 1];
        for (int i = 0; i < lengthOfStrA + 1; i++)
        {
            for (int j = 0; j < lengthOfStrB + 1; j++)
            {
                if (i == 0 || j == 0)
                {
                    table[i][j] = 0;
                }
                else if (strA.charAt(i - 1) == strB.charAt(j - 1))
                {
                    table[i][j] = table[i - 1][j - 1] + 1;
                }
                else
                {
                    table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
                }
            }
        }
        return new Pair<>(table[lengthOfStrA][lengthOfStrB], table);
    }

    private static void findAllLCS(String strA, String strB, int i, int j, int[][] table, String currentLCS,
        Set<String> allLCSResultSet)
    {
        while (i > 0 && j > 0)
        {
            if (strA.charAt(i - 1) == strB.charAt(j - 1))
            {
                currentLCS += strA.charAt(i - 1);
                i--;
                j--;
            }
            else
            {
                if (table[i - 1][j] > table[i][j - 1])
                {
                    i--;
                }
                else if (table[i - 1][j] < table[i][j - 1])
                {
                    j--;
                }
                else
                {
                    findAllLCS(strA, strB, i - 1, j, table, currentLCS, allLCSResultSet);
                    findAllLCS(strA, strB, i, j - 1, table, currentLCS, allLCSResultSet);
                    return;
                }
            }
        }
        allLCSResultSet.add(reverseString(currentLCS));
    }

    private static String reverseString(String inputString)
    {
        return new StringBuilder(inputString).reverse().toString();
    }
}

参考资料

[1]求Longest Common Subsequence长度 | DP-4
[2]输出其中一个Longest Common Subsequence
[3]输出所有Longest Common Subsequence
[4]最长公共子序列和最长公共子串
[5]LCS问题（最长公共子序列）-动态规划实现
[6]动态规划解最长公共子序列问题
[7]【动态规划】输出所有的最长公共子序列
[8]Longest Common Subsequence
[9]算法：最长公共子序列和最长公共子串（看这个）
[10]1134.最长公共子序列（输出长度）

算法 | 最长公共子序列

算法 | 最长公共子序列

题目

分析

分析一

分析二

分析三

分析四

完整代码

参考资料