самая длинная общая подпоследовательность java (рекурсивная)

Проблема, над которой я работаю, находится здесь: http://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence

в основном нам даны две строки, и нас просят найти самую длинную общую подпоследовательность. Я искал решения в Интернете и сравнивал их с моим собственным решением, и я не смог найти никаких ошибок в своем коде. Интересно, почему это все еще не работает.

А еще меня попросили решить эту задачу с помощью рекурсивных методов

Вот мой код:

public static String longestCommonSubsequence(String a, String b){
    if(a.isEmpty() || b.isEmpty()){
        return "";
    }
    if (a.substring(a.length() - 1).equals(b.substring(b.length() - 1))){
        return longestCommonSubsequence(a.substring(0, a.length() - 1), b.substring(0, b.length()
                       - 1)) + a.substring(a.length() - 1);
    } else {
        String first = longestCommonSubsequence(a, b.substring(b.length() - 1));
        String second = longestCommonSubsequence(a.substring(a.length() - 1), b);
        if(first.length() > second.length()){
            return first;
        }
        return second;
    }
}

А вот и все тестовые случаи:

Возвращаемое значение вызова

"ABCDEFG", "BGCEHAF" "BCEF"

"она продает", "ракушки" "продает"

"12345", "54321 21 54321" "123"

"высокомерный учитель", "вкусный персик", "любезный друг"

"Марти", "Элен" ""

"","Джо" ""

"Сюзи", """"

"ACGGTGTCGTGCTA", "CGTTCGGCTATCGTACGT" "CGGTTCGTGT"

с моим кодом я получил StackOverFlow для всех тестовых случаев.


java recursive-backtracking longest-substring
person Amber    schedule 22.11.2016    source источник
comment
Это может сработать. Преимуществом использования решения на основе DP является время работы.   -  person Raghav    schedule 22.11.2016
comment
Но в результате я получаю просто пустую строку. Я попытался выполнить отладку и заметил, что строка String first = longestCommonSubsequence(a, b.substring(1)) продолжает работать и обрезает буквы из строки b, пока она не станет пустой. И тогда возвращается пустая строка.   -  person Amber    schedule 22.11.2016
comment
Возможный дубликат Как сравнивать строки в Java?   -  person azurefrog    schedule 22.11.2016
comment
В частности, a.substring(0, 1) == b.substring(0, 1) всегда будет ложным.   -  person azurefrog    schedule 22.11.2016
comment
Поэтому я изменил == на .equals(), это сработало для нескольких тестов. Но, видимо, все же что-то не так, потому что это не работает для всех тестов.   -  person Amber    schedule 22.11.2016
comment
И вот, исправление ошибки выявило еще одну ошибку. Добро пожаловать в программирование. ;-)   -  person azurefrog    schedule 22.11.2016
comment
@Amber Ваш расчет LCS неверен. Пожалуйста, смотрите мое решение ниже   -  person Raghav    schedule 22.11.2016

Ответы (2)


arrow_upward
0
arrow_downward

Ваш расчет LCS неверен. В LCS вам нужно сравнивать с конца строки. Если последние символы двух строк совпадают, это означает, что это будет частью вашей LCS.

public static String longestCommonSubsequence(String a, String b) {
        int alength = a.length() - 1;
        int blength = b.length() - 1;

        if (alength < 0 || blength < 0)
            return "";

        if (a.substring(alength).equals(b.substring(blength))) {
            return longestCommonSubsequence(a.substring(0, alength), b.substring(0, blength))
                    + a.substring(alength);
        } else {
            String first = longestCommonSubsequence(a, b.substring(0, blength));
            String second = longestCommonSubsequence(a.substring(0, alength), b);
            if (first.length() > second.length()) {
                return first;
            } else {
                return second;
            }
        }
    }
person Raghav    schedule 22.11.2016
comment
Спасибо за ваше решение. Я отредактировал свой код, но он все еще не работал. Помимо этого stackflowerror, я хотел спросить, почему не работает проверка формы начала строк? - person Amber; 22.11.2016
comment
@Amber, вы не должны получать ошибки переполнения стека в приведенном выше коде. Можете ли вы опубликовать тестовый пример? Даже если вы найдете совпадение в начале строки, нет гарантии, что оно будет частью вашей LCS. - person Raghav; 22.11.2016
comment
Я разместил их. Ошибка появляется в строке 5, и я не мог понять причину. - person Amber; 22.11.2016

arrow_upward
0
arrow_downward

Вы должны изменить a.substring() на a.charAt()

public static String LCS_r(String a, String b) {
    int m = a.length() - 1;
    int n = b.length() - 1;

    if (m < 0 || n < 0)
        return "";

    if (a.charAt(m)==b.charAt(n)) {
        return LCS_r(a.substring(0, m), b.substring(0, n)) + a.substring(m);
    } 
    else {
        String s1 = LCS_r(a, b.substring(0, n));
        String s2 = LCS_r(a.substring(0, m), b);
        if (s1.length() > s2.length()) {
            return s1;
        } else {
            return s2;
        }
    }
person leo    schedule 26.01.2021