Самый длинный Общий Последующий вывод неверный результат

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 , что является неправильным результатом, поэтому что-то go не так. Ожидается, что результат будет иметь длину 4, и я не знаю точно, где я ошибся с кодом. Почему это так?

Answer 1

Я немного почистил ваш код и позволил нам go показать то, что я заметил:

#include <iostream>
#include <string>

using namespace std;

Лично я бы избежал возвращаемых значений, основанных на вопросительных знаках, в коде, потому что они не так удобочитаемы , но это всего лишь предложение.

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();

Допустим, обе строки были "AB C". Теперь второй оператор if вернет поиск по вызову AB, который вернет поиск по вызову A, который вернет «» как самую длинную подстроку A и A, в результате чего «» будет самой длинной подстрокой для AB C и AB C. Думаю, вы не после этого.

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

Вот почему я адаптировал второе утверждение if к тому, что вы имели в виду, вероятно. Здесь вы стирали последний символ, затем добавляли второй последний символ назад; Я не уверен, должно ли это быть, но так как y [последний] равен x [последний], добавление 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;
}

Попробуйте немного структурировать свой код, а теперь уточните алгоритм, потому что в нем есть некоторые ошибки алгоритма. Гудлак!

Answer 2

Я бы попробовал не стирать char и вместо этого использовать массивы - max(find(x, y[yIndex - 1]), find(x[xIndex-1], y)).