三个或更多字符串的最长公共子序列

Question

我正在尝试找出三个或更多字符串之间的最长公共子序列。维基百科上有个很好的介绍，讲解了如何处理两个字符串的情况，但我不太确定怎么把这个方法扩展到三个或更多字符串上。

有很多库可以用来找到两个字符串的最长公共子序列，所以如果可以的话，我想用其中的一个。如果我有三个字符串 A、B 和 C，先找到 A 和 B 的最长公共子序列 X，然后再找 X 和 C 的最长公共子序列，这样做是否合理，还是说这样不对？

我在 Python 中实现了这个方法，如下所示：

import difflib

def lcs(str1, str2):
    sm = difflib.SequenceMatcher()
    sm.set_seqs(str1, str2)
    matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
    return "".join(matching_blocks)

print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])

这个输出是“ba”，但实际上应该是“baa”。

Answer 1

要找到两个字符串 A 和 B 的最长公共子序列（LCS），你可以像你提供的链接那样，斜着遍历一个二维数组。这个数组里的每个元素都代表了寻找子字符串 A' 和 B' 的 LCS 问题（A 根据行号切割，B 根据列号切割）。解决这个问题需要计算数组中所有元素的值。你必须确保在计算某个数组元素的值时，所有需要的子问题都已经解决了。这就是为什么要斜着遍历这个二维数组。

这个方法也可以扩展到寻找 N 个字符串之间的最长公共子序列，但这需要一种通用的方法来遍历一个 N 维的数组，确保只有在所有需要解决的子问题都解决后，才能访问到某个元素。

除了以特定的顺序遍历 N 维数组，你还可以通过递归的方式来解决这个问题。使用递归时，保存中间结果是很重要的，因为很多分支会需要相同的中间结果。我写了一个小的 C# 示例来演示这个过程：

string lcs(string[] strings)
{
    if (strings.Length == 0)
        return "";
    if (strings.Length == 1)
        return strings[0];
    int max = -1;
    int cacheSize = 1;
    for (int i = 0; i < strings.Length; i++)
    {
        cacheSize *= strings[i].Length;
        if (strings[i].Length > max)
            max = strings[i].Length;
    }
    string[] cache = new string[cacheSize];
    int[] indexes = new int[strings.Length];
    for (int i = 0; i < indexes.Length; i++)
        indexes[i] = strings[i].Length - 1;
    return lcsBack(strings, indexes, cache);
}
string lcsBack(string[] strings, int[] indexes, string[] cache)
{
    for (int i = 0; i < indexes.Length; i++ )
        if (indexes[i] == -1)
            return "";
    bool match = true;
    for (int i = 1; i < indexes.Length; i++)
    {
        if (strings[0][indexes[0]] != strings[i][indexes[i]])
        {
            match = false;
            break;
        }
    }
    if (match)
    {
        int[] newIndexes = new int[indexes.Length];
        for (int i = 0; i < indexes.Length; i++)
            newIndexes[i] = indexes[i] - 1;
        string result = lcsBack(strings, newIndexes, cache) + strings[0][indexes[0]];
        cache[calcCachePos(indexes, strings)] = result;
        return result;
    }
    else
    {
        string[] subStrings = new string[strings.Length];
        for (int i = 0; i < strings.Length; i++)
        {
            if (indexes[i] <= 0)
                subStrings[i] = "";
            else
            {
                int[] newIndexes = new int[indexes.Length];
                for (int j = 0; j < indexes.Length; j++)
                    newIndexes[j] = indexes[j];
                newIndexes[i]--;
                int cachePos = calcCachePos(newIndexes, strings);
                if (cache[cachePos] == null)
                    subStrings[i] = lcsBack(strings, newIndexes, cache);
                else
                    subStrings[i] = cache[cachePos];
            }
        }
        string longestString = "";
        int longestLength = 0;
        for (int i = 0; i < subStrings.Length; i++)
        {
            if (subStrings[i].Length > longestLength)
            {
                longestString = subStrings[i];
                longestLength = longestString.Length;
            }
        }
        cache[calcCachePos(indexes, strings)] = longestString;
        return longestString;
    }
}
int calcCachePos(int[] indexes, string[] strings)
{
    int factor = 1;
    int pos = 0;
    for (int i = 0; i < indexes.Length; i++)
    {
        pos += indexes[i] * factor;
        factor *= strings[i].Length;
    }
    return pos;
}

我的代码示例还可以进一步优化。很多缓存的字符串是重复的，有些只是多了一个字符的重复。这在输入字符串变大时，会占用比必要更多的空间。

输入为："666222054263314443712", "5432127413542377777", "6664664565464057425"

返回的 LCS 是 "54442"

Answer 2

我刚刚为了做作业写了这个，所以这里有一个用Python实现的动态规划解决方案，效率还不错。它的时间复杂度是O(nml)，其中n、m和l分别是三个序列的长度。

这个解决方案的思路是创建一个三维数组，然后遍历这三个序列，计算出最长子序列的路径。接着，你可以通过回溯这个数组，重建出实际的子序列。

首先，你把数组初始化为全零，然后开始遍历这三个序列。在每一步遍历中，如果有匹配的地方，就把最长子序列的长度加一；如果没有匹配，就把之前步骤中的最长子序列长度继续往下带。

一旦遍历完成，你就可以开始回溯这个数组，从你走过的步骤中重建出子序列。也就是说，当你从数组的最后一个位置往回走时，每次遇到匹配的地方，就根据数组中的坐标在任意一个序列中查找，并把它加到子序列中。

def lcs3(a, b, c):
    m = len(a)
    l = len(b)
    n = len(c)
    subs = [[[0 for k in range(n+1)] for j in range(l+1)] for i in range(m+1)]

    for i, x in enumerate(a):
        for j, y in enumerate(b):
            for k, z in enumerate(c):
                if x == y and y == z:
                    subs[i+1][j+1][k+1] = subs[i][j][k] + 1
                else:
                    subs[i+1][j+1][k+1] = max(subs[i+1][j+1][k], 
                                              subs[i][j+1][k+1], 
                                              subs[i+1][j][k+1])
    # return subs[-1][-1][-1] #if you only need the length of the lcs
    lcs = ""
    while m > 0 and l > 0 and n > 0:
        step = subs[m][l][n]
        if step == subs[m-1][l][n]:
            m -= 1
        elif step == subs[m][l-1][n]:
            l -= 1
        elif step == subs[m][l][n-1]:
            n -= 1
        else:
            lcs += str(a[m-1])
            m -= 1
            l -= 1
            n -= 1

    return lcs[::-1]

Answer 3

只需要把这个递归关系进行概括就可以了。

对于三个字符串来说：

dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if A[i] = B[j] = C[k]
              max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise

从这里出发，应该很容易就能推广到更多的字符串。