最长公共子序列输出错误结果

Question

我一直在尝试使用如下递归来解决 LCS 问题：

#include <iostream>
#include <string>

using namespace std;

string max(string x, string y) {
    return x.size() <= y.size() ? y : x;
}

string find(string x, string y) {
    // Find longest Sub Sequence
    int firstSize = x.size();
    int secondSize = y.size();

    if (firstSize == 0 || secondSize == 0) {
        return "";
    }

    if (x[firstSize - 1] == y[secondSize - 1]) {

        char temp = x[firstSize - 1];

        return find(x.erase(firstSize-1), y.erase(secondSize-1)) + temp;
    }

    return max(find(x, y.erase(secondSize - 1)), find(x.erase(firstSize - 1), y));
}

int main()
{
    string x = "ABCBDAB";
    string y = "BDCABA";

    string result = find(x, y);

    cout << "result = "<<result<< endl;

    return 0;
}

这个算法看起来是对的，但是输出ABA后面是错误的结果，所以出问题了。预期结果是后续的长度为 4，我不知道我的代码到底哪里出错了。为什么会这样？

Answer 1

我会尝试不擦除字符而是使用数组 - max(find(x, y[yIndex - 1]), find(x[xIndex-1], y))。

Answer 2

我稍微清理了你的代码，让我们看看我注意到的内容：

#include <iostream>
#include <string>

using namespace std;

我个人会避免在代码中使用基于问号的 return 值，因为它们可读性差，但这只是一个建议。

string max(string x, string y)
//  Return biggest string
{
    if (x.size() <= y.size())
        return y;
    else
        return x;
}

string find(string x, string y)
//  Find longest Sub Sequence
{
    int xSize = x.size();
    int ySize = y.size();

假设这两个字符串都是 "ABC"。现在第二个 if 语句将 return 在 AB 调用中查找，这将 return 在 A 调用中查找，这将 return "" 作为 A 和 A 的最长子串，导致"" 作为 ABC 和 ABC 的最长子串。我猜你不是在追这个。

    if (xSize == 0 || ySize == 0)
        return "";

这可能就是为什么我根据您的意思改编第二个 if 语句的原因。在这里你擦除最后一个字符，然后添加倒数第二个字符；我不确定这是否应该如此，但由于 y[last] 等于 x[last]，在删除它的 last 之后附加 y，x 的最后一个字符就是 y 本身。

    else if (x[xSize - 1] == y[ySize - 1])
        return find(x.erase(xSize - 1), y);

然后这个变量只被使用了一次：char temp = x[xSize - 1]。您可能希望将其内联编写，这样您就不必在必要时创建变量和注释；但这只是代码风格偏好。

    else
        return max(find(x, y.erase(ySize - 1)), find(x.erase(xSize - 1), y));
}

int main()
{
    string x = "ABCBDAB";
    string y = "BDCABA";

    cout << "result = " << find(x, y) << endl;

    return 0;
}

尝试将您的代码结构化一些，现在改进算法，因为其中有一些算法错误。祝你好运！

最长公共子序列输出错误结果

Longest Common Subsequent output wrong result

c++

string

algorithm

subsequence

lcs