Longest common subsequence prolem

Question

What is longest common subsequence for these 2 strings {xaybadfeg, abcdefg}. Isn't it "abdeg"? I am using this algorithm (the dynamic programming technique) to find the solution. It returns "adeg" as the answer. Is my understanding of subsequence wrong? Is my algorithm wrong? Am I missing something? Should I corner case for this type of input?

Dynamic programming code

#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;
}

Any input is greatly appreciated. Thanks!

fgb fgb · Accepted Answer · 2016-07-09T20:37:40

"abdeg" is a longest common subsequence, but there are others like "abdfg".

The backtracking is wrong. If you output the values of i and j, then they are becoming negative, and then invalid string indexes are accessed.

Subtracting 1 from the string indexes should give the right answer. I've also change the || condition to an &&.

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--;
    }
}

Longest common subsequence prolem

2 Answers