Самая длинная общая последовательность подпоследовательностей

Question

Какая самая длинная общая подпоследовательность для этих 2 строк {xaybadfeg, abcdefg}. Разве это не "абдег"? Я использую этот алгоритм (метод динамического программирования), чтобы найти решение. Он возвращает "АДЕГ" в качестве ответа. Мое понимание подпоследовательности неверно? Мой алгоритм неверен? Я что-то пропустил? Должен ли я угловой случай для этого типа ввода?

Динамический программный код

#include <iostream>
#include <stack>
using namespace std;

void LCS(string str1, string str2){
    int out[100][100] = {};
    for (int i = 0; i <= str1.size(); i++){
        for (int j = 0; j <= str2.size(); j++){
            if (i == 0 || j == 0)
                out[i][j] = 0;
            else{
                if (str1[i-1] == str2[j-1]){
                    if (out[i][j - 1] > out[i - 1][j])
                        out[i][j] = out[i][j - 1] + 1;
                    else
                        out[i][j] = out[i - 1][j] + 1;
                }
                else{
                    if (out[i][j - 1] > out[i - 1][j])
                        out[i][j] = out[i][j - 1];
                    else
                        out[i][j] = out[i - 1][j];
                }
            }
        }
    }

    //Backtracing to print the numbers
    int i = str1.size()-1, j = str2.size()-1;
    std::string subSeqStr="";
    while (i >= 0 || j >= 0){
        if (str2[j] != str1[i]){
            if (out[i][j - 1] > out[i - 1][j])
                j--;
            else
                i--;
        }
        else{
            subSeqStr.insert(subSeqStr.begin(), str2[j]);
            i--; j--;
        }
    }
    std::cout << "The least common subsequence is: " << subSeqStr<< std::endl;
}

int main(){
    string str1 = "xaybadfeg";
    string str2 = "abcdefg";
    LCS(str1,str2);
    getchar();
    return 0;
}

Любой вклад с благодарностью. Спасибо!

Answer 1

"abdeg" - самая длинная общая подпоследовательность, но есть и другие, например "abdfg".

Отступление неверно. Если вы выводите значения i и j, то они становятся отрицательными, а затем доступ к недопустимым строковым индексам.

Вычитание 1 из строковых индексов должно дать правильный ответ. Я также изменил || условие к &&.

int i = str1.size(), j = str2.size();
std::string subSeqStr="";
while (i > 0 && j > 0){
    if (str2[j - 1] != str1[i - 1]) {
        if (out[i][j - 1] > out[i - 1][j])
            j--;
        else
            i--;
    }
    else{
        subSeqStr.insert(subSeqStr.begin(), str2[j - 1]);
        i--; j--;
    }
}

Answer 2

Это выглядит неправильно:

if (i == 0 || j == 0)
    out[i][j] = 0;

Ваши строки индексируются, начиная с 0, поэтому вы не можете применять формулу, как это показано в большинстве учебников и учебных пособий, в которых индексация начинается с 1.

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