By Ali Eser


2019-07-11 18:49:47 8 Comments

I have a really easy code for finding the LCS. the problem is not with the algorithm, but rather something else. The code stops working after taking the last input in the for loop.

I tried to find why this happens, and saw that when I commented out my LCS_string function, the code works "fine". However, this line of code is after the printing out, so I don't get how or why it affects the printing out.

vector<int> str1, str2;
vector<vector<int> > dp;
stack<int> s;

int LCS(int a, int b){
    if(dp[a][b] != -1){
        return dp[a][b];
    }
    if(a == 0 || b == 0){
        dp[a][b] = 0;
        return dp[a][b];
    }
    if(str1[a-1] == str2[b-1]){
        dp[a][b] = LCS(a-1, b-1) + 1;
        return dp[a][b];
    }
    dp[a][b] = max( LCS(a-1, b), LCS(a, b-1) );
    return dp[a][b];
}

void LCS_string(int a, int b){
    cout << "in lcs_string with: " << a << "  " << b << endl;
    if(dp[a][b] > dp[a-1][b] && dp[a][b] > dp[a][b-1]){
        s.push( str1[a-1] );//could also be y[b] as they are the same element
        LCS_string(a-1, b-1);
        return;
    }
    if(dp[a-1][b] > dp[a][b-1]){
        LCS_string(a-1, b);
        return;
    }
    else{
        LCS_string(a, b-1);
        return;
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    int temp;
    for(int i = 0; i < n; i++){
        cin >> temp;
        str1.push_back(temp);
    }
    for(int i = 0; i < m; i++){
        cin >> temp;
        cout << i;
        str2.push_back(temp);
        cout << "done" << endl;//doesnt print anything when i == m-1
    }
    cout << "end of inputting" << endl;//is not outputted
    dp.resize( n + 1, vector<int>( m + 1, -1 ) );
    LCS( n, m );
    LCS_string(n, m);//when this line is commented out, the code works
    while(!s.empty()){
        cout << s.top();
        s.pop();
    }
}

I get no error messages or whatsoever, the program terminates without giving any output.

0 comments

Related Questions

Sponsored Content

15 Answered Questions

[SOLVED] How can I profile C++ code running on Linux?

  • 2008-12-17 20:29:24
  • Gabriel Isenberg
  • 471967 View
  • 1665 Score
  • 15 Answer
  • Tags:   c++ unix profiling

7 Answered Questions

1 Answered Questions

[SOLVED] How to fix the error of not taking value at 0 position in loop

  • 2019-04-15 17:34:34
  • Bilal Khan
  • 26 View
  • -2 Score
  • 1 Answer
  • Tags:   c++

10 Answered Questions

10 Answered Questions

1 Answered Questions

[SOLVED] Exception basics: why is the while loop turning into an infinite loop?

  • 2018-05-23 04:33:20
  • Renato Moraes
  • 73 View
  • 0 Score
  • 1 Answer
  • Tags:   c++ loops while-loop

1 Answered Questions

[SOLVED] Cannot wrap my head around how cin.get and cout are working here

  • 2018-04-05 13:08:35
  • Mohammed Aquib Azad
  • 46 View
  • -4 Score
  • 1 Answer
  • Tags:   c++ iostream

2 Answered Questions

[SOLVED] Operator "<<" overloading return type

  • 2014-12-01 11:20:20
  • Hemant Bhargava
  • 327 View
  • 3 Score
  • 2 Answer
  • Tags:   c++ c++11

2 Answered Questions

[SOLVED] C++; Using strings getline() not working with file input

2 Answered Questions

[SOLVED] Super weird error when handling strings

Sponsored Content