c++ - 在字符串中查找所有具有最大长度的有序序列

Question

我有以下问题需要解决: 有两个任意长度的任意内容的字符串。我需要找到所有具有最大长度的有序序列，它出现在两个字符串中。

示例 1: 输入:“a1b2c3”“1a2b3c” 输出:“123”“12c”“1b3”“1bc”“a23”“a2c”“ab3”“abc”

示例 2: 输入:“cadb”“abcd” 输出:“ab”“ad”“cd”

我用两个循环直接写了它，递归，然后删除重复项和作为较大结果一部分的结果(例如“abc”序列包含“ab”“ac”和“bc”序列，所以我正在过滤那些)

// "match" argument here used as temporary buffer
void match_recursive(set<string> &matches, string &match, const string &a_str1, const string &a_str2, size_t a_pos1, size_t a_pos2)
{
    bool added = false;

    for(size_t i = a_pos1; i < a_str1.length(); ++i)
    {
        for(size_t j = a_pos2; j < a_str2.length(); ++j)
        {
            if(a_str1[i] == a_str2[j])
            {
                match.push_back(a_str1[i]);

                if(i < a_str1.length() - 1 && j < a_str2.length() - 1)
                    match_recursive(matches, match, a_str1, a_str2, i + 1, j + 1);
                else
                    matches.emplace(match);
                added = true;

                match.pop_back();
            }
        }
    }

    if(!added)
        matches.emplace(match);
}

这个函数解决了问题，但是复杂度 Not Acceptable 。例如“0q0e0t0c0a0d0a0d0i0e0o0p0z0”“0w0r0y0d0s0a0b0w0k0f0.0k0x0”的解决方案在我的机器上需要 28 秒(调试目标，但无论如何这非常慢)。我认为这个问题应该有一些简单的算法，但不知何故我在网上找不到任何算法。

你们能指出我正确的方向吗？

Answer 1

查找“最长公共(public)子序列 (LCS)”问题，例如http://en.wikipedia.org/wiki/Longest_common_subsequence_problem并查看动态规划解决方案如何找到两个序列的 LCS，基于有效地构建解决方案，首先简单地获取每个序列的第一个字符的 LCS，然后为越来越长的对构建 LCS 解决方案两个序列的前缀。您需要做的唯一修改是，当您从先前计算的较早前缀对的 LCS 解决方案中获取当前前缀对的 LCS 时，您需要存储较早前缀对的所有先前 LCS 字符串，然后组合这些集合将 LCS 字符串(可能带有添加的字符)组合成您为当前前缀对存储的一组 LCS 字符串。这将有效地解决您的问题。您可以通过首先获取单个 LCS 并获取整个 LCS 长度，然后找到所有有助于获取 LCS 长度的计算路径的所有较早的前缀对，然后返回并重复动态编程迭代来更有效地解决问题只是为了那些前缀对，这次跟踪所有可能的 LCS 序列，就像我之前描述的那样。