Проблема самой длинной подпоследовательности, если длины разные - PullRequest
Новая
       65

Проблема самой длинной подпоследовательности, если длины разные

0 голосов
/ 01 ноября 2019

Пусть входные последовательности будут X[0..m-1] и Y[0..n-1] длины m и n соответственно. И пусть L(X[0..m-1], Y[0..n-1]) будет длиной LCS двух последовательностей X и Y. Ниже приводится рекурсивное определение L(X[0..m-1], Y[0..n-1]).

Если последние символы обеих последовательностей совпадают (или X[m-1] == Y[n-1]), то L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

Если последние символы обеих последовательностей не совпадают (илиX[m-1] != Y[n-1]) затем

L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]) )

Как решить проблему, если длины разные? и как распечатать соответствующие последовательности

1 Ответ

0 голосов
/ 01 ноября 2019

Неважно, если длина входных строк одинакова или нет, и это учитывается базовым случаем рекурсии. 

if (m == 0 || n == 0) 
    return 0;

Если мы достигнем конца любогоодна из строк, рекурсия останавливается и раскручивается оттуда.

Также пример, который вы упомянули в комментарии:

ABCEFG и ABXDE Сначала мы сравниваем последний символ из обоихстрока. В этом случае они не одинаковы.

Итак, мы попробуем два случая:

  • Удалить последний символ из первой строки и сравнить его со вторым.
  • Удалить последний символ из второй строки и сравнить его с первым.

И вернуть максимум из обоих случаев.

(В качестве примечания, если последнийсовпадение символа, мы добавили бы 1 к нашему ответу и удалили последний символ из обеих строк)

Этот процесс продолжается до тех пор, пока какая-либо строка не достигнет своего конца, и в этом случае базовый случай вашей рекурсии будет выполнени рекурсия возвращается.

Так что не имеет значения, одинакова ли исходная длина строки.

...