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

Question

Что такое самая длинная общая подпоследовательность для этих двух строк {xaybadfeg, abcdefg}. Разве это не «абдег»? Я использую этот алгоритм (метод динамического программирования), чтобы найти решение. Он возвращает «adeg» в качестве ответа. Является ли мое понимание подпоследовательности неправильным? Является ли мой алгоритм неправильным? Я что-то упускаю? Должен ли я использовать угловой корпус для ввода такого типа?

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

#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

Это выглядит не так:

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

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

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

Answer 2

«Абдег» - самая длинная общая подпоследовательность, но есть и другие, такие как «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--; 
    } 
}