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

Question

Проблемы я работаю здесь: 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"

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

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

"высокомерное учитель", "вкусный персик" "ecious каждый"

" Марти», "Helene" ""

"", "Джо" ""

"Сюзи", "" ""

"ACGGTGTCGTGCTA", "CGTTCGGCTATCGTACGT" "CGGTTCGTGT"

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

Answer 1

Ваш расчет 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; 
      } 
     } 
    }