Error in running a test case In LONGEST COMMON SUBSTRING

Question

I need to solve a question that asks for code finding the longest common substring between 2 strings:

My code is not running for one test case given below:

17 60
KXCGMTMVVGFQQWSPD
JXZADDUKVLQPKUZJZHWSUTPCAFSYAIBJHAMMEGWBTPQELRNKBLDXGUZGCSEC

The code is given below

//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution{
    public:
    // This is the recursive approach 
    int longest( string s1 , string s2  , int i,  int j , int & ans ,vector<vector<int>> &dp  )
    {
        if(i<0 && j<0)
        {
            return 1;
        }
        if(i<0|| j<0)
        {
            return 0;
        }
        if(dp[i][j]!=-1)
        {
            return dp[i][j];
        }
        if(s1[i]==s2[j])
        {
            int k = 1+longest(s1,s2 ,i-1 ,j-1 ,ans ,dp);
            ans = max(ans, k);
            dp[i][j]=k ;
            return k ;
        }
        int a =longest(s1, s2 , i-1,j , ans,dp);
        int b = longest(s1,s2 ,i ,j-1,ans,dp) ;
        dp[i][j]=0;
        return 0;
    }
     // Here is the tabulation approach 
    int longestCommonSubstr (string s1, string s2, int n, int m)
    {
        // your code here
        int ans=0;
        vector<vector<int>> dp (s1.length(),vector<int>( s2.length(),-1));
        int k = longest(s1,s2,n-1,m-1,ans,dp);
        return ans;
        /*int ans =0;
        vector<int> row1(s2.length()+1 ,0);
        vector<int> row2(s2.length()+1 , 0);
        for( int i =0;i<n ;i++)
        {
            for( int j =0;j<m ;j++)
            {
                if(s1[i]==s2[j])
                {
                    int k =1+row1[j];
                    ans = max(ans,k);
                    row2[j+1]=k; 
                }
                else
                {
                    row2[j+1]=0;
                }
            }
            row1= row2 ;
        }
        return ans;*/
    }
};

//{ Driver Code Starts.

int main()
{
    int t; cin >> t;
    while (t--)
    {
        int n, m; cin >> n >> m;
        string s1, s2;
        cin >> s1 >> s2;
        Solution ob;

        cout << ob.longestCommonSubstr (s1, s2, n, m) << endl;
    }
}
// Contributed By: Pranay Bansal

// } Driver Code Ends

I have tried but the memoization technique is failing for one of the test cases but the tabulation technique does work. So please refer to the code and correct it.

Please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) The resource that taught you those are bad resource for learning the basics of C++. — Some programmer dude, Apr 01 '23 at 10:32
As for your problem, if you know the input that causes the problem then hard-code it into your program, and [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your program. For example by using a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through your code line by line, while monitoring variables and their values, to see what really happens. — Some programmer dude, Apr 01 '23 at 10:34
And please always build with extra warning enabled. You [have a couple](https://godbolt.org/z/c3df6roP5) that perhaps are relevant? — Some programmer dude, Apr 01 '23 at 10:46

score 0 · Answer 1 · answered Apr 24 '23 at 01:04

I am still not at the level of things like classes in C++, but there seems to be a much easier solution to this test case different from yours. My code is guaranteed to work even if it might be slow because it uses brute force checking of each substring of the shorter string (checking the longer one takes time and the substring could be longer than the shorter string, producing an error). However, I tried to speed it up by checking the shorter string with backward sizes to find the first string that is common in both which is also the largest common substring. That means the code no longer needs more runs of my loops. Your test case runs in reasonable time limits and correct results here: Run Demo with your test case at bottom of the page

#include <iostream>
#include <string>
int discard; //you can access string length using the function
std::string str1, str2, temp;
int main () {
    std::cin >> discard >> discard >> str1 >> str2;
    if (str1.length() > str2.length()) {//if str1 is not the shorter one, make it the shorter one by switching
        temp = str2;
        str2 = str1;
        str1 = temp;
    }
    for (int size = str1.length(); size >= 1; size--) { //backwards length checking
        for (int j = 0; j <= str1.length() - size; j++) { //start position
            temp = str1.substr(j, size); //the substring
            if (str2.find(temp) != std::string::npos) { //if the substring works, it is the largest
                std::cout << "The longest common substring: " << temp; //output and end program
                return 0;
            }
        }
    }
    std::cout << "No Common Substring";
    return 0;
}

Error in running a test case In LONGEST COMMON SUBSTRING

1 Answers1