c++ - 最长公共(public)子字符串的递归解决方案中的错误

问题:给定两个字符串“X”和“Y”，找到最长的公共(public)子字符串的长度。
我的解决方案一直运行，没有达到基本条件。我不明白为什么会这样？
我看过DP解决方案，但在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));
        }


    }
}

初始参数:
str1 =“AABC”
str2 =“ABCD”

i_1 = 0(第一个字符串的索引)
i_2 = 0(第二个字符串的索引)
c_lcs = 0(当前公共(public)子串的长度)
lcs = 0(最长公共(public)子串的长度)

最佳答案

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

在第一个调用中，仅应增加i_1，而在第二个调用中，应仅增加i_2。由于您使用++，因此在两个调用中均传递了递增的i_1。
您应该了解，在第一次调用++i_1后，在第二次调用lcs_calc()时，i_1也会作为增量值传递，这不是您想要的。

另外，您不需要其他情况。

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));
}

关于c++ - 最长公共(public)子字符串的递归解决方案中的错误，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48258718/