Longest Common Subsequence is not showing the result

Question

I have written this code using dynamic programming approach and I think the logic is good but the code is not displaying the result. The code is as follows:

#include <iostream>
using namespace std;

void LCS(int input1[], int input2[], int n, int m) {
    int L[n + 1][m + 1];  /*This matrix stores the length of common subsequences*/
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (input1[i - 1] == input2[j - 1]) 
                L[i][j] = 1 + L[i - 1][j - 1]; 
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
    int index = L[n][m];
    int lcs[index];
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (input1[i - 1] == input2[j - 1]) {
            lcs[index - 1] = input1[i - 1];
            i--;
            j--;
            index--;
        } else if (L[i - 1][j] > L[i][j - 1])
            i--;
        else
            j--;

    }
    for (int i = 0; i < index; i++){
        cout << lcs[i];
    }

}
int main() {
    int n, m;
    cin >> n >> m;
    int input1[n], input2[m]; /*two arrays from which longest subsequnce is to be found*/
    for (int i = 0; i < n; i++)
        cin >> input1[i];
    for (int i = 0; i < m; i++)
        cin >> input2[i];
    LCS(input1, input2, n, m);
    return 0;
}

The code terminates without showing any result!

I even switched to a different IDE but its the same. What is wrong with this?

The right tool to solve such problems is your debugger. You should step through your code line-by-line *before* asking on Stack Overflow. For more help, please read [How to debug small programs (by Eric Lippert)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). At a minimum, you should \[edit] your question to include a [Minimal, Complete, and Verifiable](http://stackoverflow.com/help/mcve) example that reproduces your problem, along with the observations you made in the debugger. — πάντα ῥεῖ, Sep 27 '16 at 17:18
You could also add printf statement to check if your matrix L is correct after the two first loops. — Renaud, Sep 27 '16 at 17:27
Also I can't spot how this is related to [tag:dynamic-programming] — πάντα ῥεῖ, Sep 27 '16 at 17:29
check your index variable, if your program terminated, "without showing any result" may be caused your last loop doesn't work — malioboro, Sep 27 '16 at 17:31
@πάνταῥεῖ This is a classic dp problem. https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution — Saeid, Sep 27 '16 at 17:31
@πάνταῥεῖ This is a bottom-up approach. see http://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-bottom-up-vs-top-down-approaches — Saeid, Sep 27 '16 at 17:40
Your example isn't self-contained. Instead of reading some unspecified values from `std::cin`, please use constants to make it a [mcve]. Thanks. — Toby Speight, Sep 28 '16 at 16:27

Saeid · Accepted Answer · 2016-09-27T17:43:56.907

You are modifying the index variable. Create a copy of it and modify that. Here I used temp.

int index = L[n][m];
int temp = index;
int lcs[index];
int i = n, j = m;
while (i > 0 && j > 0) {
    if (input1[i - 1] == input2[j - 1]) {
        lcs[temp - 1] = input1[i - 1];
        i--;
        j--;
        temp--;
    } else if (L[i - 1][j] > L[i][j - 1])
        i--;
    else
        j--;

}
for (int i = 0; i < index; i++){
    cout << lcs[i];
}

In your version index is decremented to zero when you want to print the result so nothing will be printed.

Longest Common Subsequence is not showing the result

1 Answers1