Я пытаюсь найти самую длинную общую подстроку из двух строк с использованием рекурсии и DP. Обратите внимание, что я не имею в виду самую длинную непрерывную подпоследовательность. Таким образом, если две строки былиСамая длинная общая подстрока с использованием рекурсии и DP
String s1 = "abcdf"; String s2 = "bzcdf"
Longest Common Substring == "cdf" (not "bcdf").
Basically they have to be continuous elements
Я пытаюсь сделать это с помощью рекурсии и откаты. Однако проблема заключается в том, что если я использую рекурсию, например, ниже, то +1 добавляются заранее в фрейм, то есть выше в стеке вызовов, и не знают о том, являются ли персонажи действительно непрерывными элементами или нет , Итак, перейдя к примеру выше, «bcdf» будет ответом.
public class ThisIsLongestCommonSubsequence_NotSubstring {
public static void main(String[] args) {
String s1 = "abcdgh";
String s2 = "abefgh";
System.out.println(fun(s1, s1.length()-1, s2, s2.length()-1));
}
static int fun(String s1, int i, String s2, int j)
{
if(i == -1 || j == -1)
return 0;
int ret = 0;
if(s1.charAt(i) == s2.charAt(j))
ret = fun(s1, i-1, s2, j-1) + 1;
else
ret = max(fun(s1, i-1, s2, j), fun(s1, i, s2, j-1));
return ret;
}
static int max(int a, int b)
{
return a>b?a:b;
}
}
На данный момент приведенный ниже код является тем, что я придумал. Обратите внимание, как я сброшу счет до 0, каждый раз, когда я нахожу несоответствие. И отслеживайте количество совпадающих символов, используя переменную с именем int count, и записывайте самое высокое значение в любой точке программы, используя переменную с именем int maxcount. Мой код ниже.
public class LongestContinuousSubstringGlobalvariable {
static int maxcount = 0;
public static void main(String[] args) {
String s1 = "abcdghijl";
String s2 = "abefghijk";
fun(s1, s2, s1.length()-1, s2.length()-1, 0);
System.out.println("maxcount == "+maxcount);
}
static void fun(String s1, String s2, int i, int j, int count)
{
if(i == -1 || j==-1)
return;
if(s1.charAt(i) == s2.charAt(j))
{
if(count+1 > maxcount)
maxcount = count+1;
fun(s1, s2, i-1, j-1, count+1);
}
else
{
fun(s1, s2, i-1, j, 0);
fun(s1, s2, i, j-1, 0);
}
}
}
Это прекрасно работает. Тем не менее, есть несколько вещей, которые мне не нравится мой код
- Использование глобального переменный (статический INT MAXCOUNT) для сравнения разных кадров
- Я не думаю, что это реально динамическое программирование или возвраты , так как нижний кадр не , возвращающий, он выводит на более высокий кадр, который затем решает, что с ним делать.
Просьба дать мне свои данные о том, как я могу достичь этого, не используя глобальную переменную и используя обратный трассировку.
PS: Я знаю о других подходах к проблеме, как сохранение матрицы, и делать что-то вроде
M [я] [J] = M [I-1] [J-1] +1 if (str [i] == str [j])
Целью является не решение проблемы, а поиск элегантного рекурсивного/обратного отслеживания.
Возможный дубликат [Серия Common Substring] (http://stackoverflow.com/questions/22319437/longest-common-substring) – Prune