string - 一系列字符串的最长公共子序列

Question

对于 2 个字符串的最长公共子序列，我在网上找到了很多示例，我相信我理解了解决方案。
我不明白的是，将这个问题应用于N字符串的正确方法是什么？是否以某种方式应用了相同的解决方案？如何？解决方案不同吗？什么？

Answer 1

当输入具有任意数量的字符串时，此问题变得NP-hard 。只有当输入具有固定数量的字符串时，这个问题才变得容易处理。如果输入有 k 个字符串，我们可以通过使用 ak 维数组来应用相同的 DP 技术来存储子问题的最优解。

参考：最长公共子序列问题

Answer 2

要找到 2 个字符串 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"