0

I am trying to implement longest common subsequence problem iteratively and recursively. But my code keeps giving me Error Code -1073741819 (0xC0000005). I have tried to dry run it and the logic seems correct but I am not getting the desired results. Here is what I implemented:-

/* Dynamic Programming Solution */


#include <iostream>
#include <string>
#include <vector>
using namespace std ;

void input();
void lcs(string s1,string s2,unsigned int m ,unsigned int n);

void input(){
    string s1 , s2 ;
    unsigned int m , n ;
    cin >> s1 ;
    cout << flush ;
    cin >> s2 ;
    cout << flush ;
    m = s1.length();
    n = s2.length();
    lcs(s1,s2,m,n);
    // to main
}

// Tabulated function

void lcs(string s1,string s2,unsigned int m ,unsigned int n){
    vector <vector<int>> memo(m + 1);
    vector <int> v(n + 1);
    for(int i = 0 ; i <= m ; i++ ){
        memo.push_back(v);
    }
    for(int i = 0 ; i <= n ; i++ ){
        memo[0].push_back(0) ;
    }
    for(int i = 0 ; i < m ; i++ ) {
        memo[i].push_back(0);
    }
    for(int i = 1 ; i <= m ; i++ ){
        for(int j = 1 ; j <= n ; j++ ){
            if(s1[i - 1] == s2[j - 1]){
                memo[i][j] = 1 + memo[i - 1][j - 1];
            }else{
                memo[i][j] = max(memo[i - 1][j],memo[i][j - 1]);
            }
        }
    }
    cout << memo[m][n];
}

int main(){
    input();
    return 0 ;
}
CodeX
  • 1
  • 2
  • youre creating vectors of appropriate size and then using push_back into them. that seems wrong. is that what you meant to do? or did you mean to assign to those? (or maybe call reserve(...) instead). my suspicion is youre accessing out of bounds on those entries that were default initialized when you created the vector. – Borgleader Jun 02 '22 at 18:50
  • 1
    it would also be useful to know on which line youre crashing – Borgleader Jun 02 '22 at 18:52
  • 2
    *I have tried to dry run it and the logic seems correct but I am not getting the desired results.* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). Don't do "dry runs". We are humans, our eyes may get tired, we may become distracted, the cat may walk across our laps while we are going through the code, etc. Invest time in learning how to use the debugger that comes with your compiler toolset. – PaulMcKenzie Jun 02 '22 at 18:59
  • I am trying to assign zero to all the entries in the first row and the first column. – CodeX Jun 02 '22 at 18:59
  • 2
    `vector > memo(m + 1);` -- This already creates `m+1` vectors of integers. Are you aware of this? If you know this, as mentioned, calling `push_back` adds *more* vectors to an already sized vector. – PaulMcKenzie Jun 02 '22 at 19:01
  • I *think* both of those decls *and* the ensuing for loops can be replaced with `vector > memo(m + 1, vector(n+1));`. No push-backs. – WhozCraig Jun 02 '22 at 19:07
  • `0xC0000005` is Access Violation: [https://james.darpinian.com/decoder/?q=0xC0000005](https://james.darpinian.com/decoder/?q=0xC0000005) – drescherjm Jun 02 '22 at 19:12
  • Yes this is working just fine. Thankyou very much ! @WhozCraig – CodeX Jun 02 '22 at 19:16
  • 1
    The other reason for using a debugger: It doesn't care about your assumptions. Any assumptions made when writing code will likely follow through to your subsequent re-reading of the code when looking for a bug. If an assumption is wrong, the debugger will show you as soon as you step over the mistake and see your expectations violated.. – user4581301 Jun 02 '22 at 19:23

0 Answers0