Error in Recursive solution to Longest Common Substring

2
votes

Problem: Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.
My solution keeps running and doesn't reach the base condition. I don't understand why that is?

I have looked at the DP solution but cannot find a satisfactory recursive solution for this problem on the internet.

int lcs_calc(string str1, string str2, int i_1, int i_2, int lcs, int c_lcs)
{

    if (i_1 >= str1.length() || i_2 >= str2.length())
    {
        //end. base cond
        return lcs;
    }
    if (str1[i_1] == str2[i_2])
    {
        c_lcs++;
        if (c_lcs > lcs) lcs = c_lcs;
        return lcs_calc(str1, str2, ++i_1, ++i_2, lcs, c_lcs);
    }
    else
    {
        if (c_lcs == 0)
        {
            return max(lcs_calc(str1, str2, ++i_1, i_2, lcs, c_lcs), lcs_calc(str1, str2, i_1, ++i_2, lcs, c_lcs));
        }
        else
        {
            c_lcs = 0;
            return max(lcs_calc(str1, str2, --i_1, i_2, lcs, c_lcs), lcs_calc(str1, str2, i_1, --i_2, lcs, c_lcs));
        }


    }
}



Initial Parameters:

str1 = "AABC"
str2 = "ABCD"

i_1 = 0 (index for 1st string)
i_2 = 0 (index for 2nd string)
c_lcs = 0 (length of current common substring)
lcs = 0 (length of longest common substring)

2
c++recursionsubstringdynamic-programming
Have you tried to step through the code in a debugger? It can be quite a hassle with recursive functions, especially if you have as many calls as you have, but it's still something that every programmer needs to be able to do. - Some programmer dude
I don't think you'll ever reach your base condition except if one of the string is a substring of the other (try with "ABC" and "AABCDE") - assuming no other problem with your code, that should terminate nicely. You need to formulate a different base condition. - falopsy
The string's are passed in by value, then, why do you need to have i_1 and i_2 ? why not mutate the string and check s[0] == p[0] if they are mutate both by doing s.substr(1) and p.substr(1) if not skip s[i] and also check skip p[i]. In the base case s.empty or p.empty return 1 and add it. You have made this very complicated. - Samer Tufail
On a side note, are you after the longest common substring or longest common subsequence, the above attempt seems to point to the latter. - Samer Tufail

2 Answers

3
votes
return max(lcs_calc(str1, str2, ++i_1, i_2, lcs, c_lcs), lcs_calc(str1, str2, i_1, ++i_2, lcs, c_lcs));

In the first call, only i_1 should be incremented, and in the second call only i_2 should be incremented.Since you use ++, incremented i_1 is passed in both calls. You should understand that once you do ++i_1 in the first call, in the second call to lcs_calc() i_1 is passed as incremented value as well which is not what you want.

Also you don't need the other case.

else
{
 return max(lcs_calc(str1, str2, i_1+1, i_2, lcs, c_lcs), lcs_calc(str1, str2, i_1, i_2+1, lcs, c_lcs));
}
1
votes

What is striking is that you decrease indexes while calling the function recursively. This should not be done as the indexes decrease automatically while returning. You should continue with increasing one index and afterwards continue with increasing the other index when the characters are not the same.

Something like (focusing on recursing, not correctness):

if (length reached): return c_lcs
if same: lcs = rec(str1, str2, i1+1, i2+1, c_lcs)
lcs = max(lcs, rec(str1, str2, i1+1, i2, 0))
lcs = max(lcs, rec(str1, str2, i1, i2+1, 0))
return lcs;