Longest Common Substring - Почему этот рекурсивный код неправильный? - PullRequest
Новая
       47

Longest Common Substring - Почему этот рекурсивный код неправильный?

0 голосов
/ 26 апреля 2020

Я видел два похожих вопроса. Одна была Самая длинная общая подпоследовательность , а другая была Самая длинная общая подстрока . Я понял рекурсивный подход, использованный в Longest Common Subsequence. Поэтому я попытался реализовать самую длинную общую подстроку, используя тот же подход. Это мой код: 

    static int lcs(int m, int n){
        if(m<=0 || n<=0) return 0;

        if(X.charAt(m-1)==Y.charAt(n-1)){
            if(m-2>=0 && n-2>=0 && X.charAt(m-2)==Y.charAt(n-2)){
                return 1 + lcs(m-1,n-1);
            }else{
                return 1;
            }
        }

        return Math.max(lcs(m-1,n),lcs(m,n-1));

    }

Я проверяю, X[m-1]==Y[n-1] или нет, тогда я проверяю, X[m-2]==Y[n-2] или нет, если он равен, то он будет гарантировать, что рассматриваемые индексы являются последовательными и это подстрока. Этот код может пройти некоторые тестовые случаи, но не все. В чем заключается ошибка в этом коде и почему проходят некоторые тесты? 

I tried ABCDGH and ACDGHR - My code gave correct output for this ie. 4
...