Найти самую длинную подпоследовательность строки, которая является подстрокой другой строки

Опубликовано: 22 Сентября, 2022

Даны две строки X и Y , состоящие из N и M символов, задача состоит в том, чтобы найти самую длинную подпоследовательность строки X, которая является подстрокой строки Y .

Примеры:

Input: X = “ABCD”, Y = “ACDBDCD”
Output: ACD
Explanation:
“ACD” is longest subsequence of X which is substring of Y.

Input: X = A, Y = A
Output: A

Наивный подход: самый простой подход к решению данной проблемы — найти все подпоследовательности заданной строки X и распечатать среди всех сгенерированных подпоследовательностей ту подпоследовательность, которая имеет максимальную длину и является подстрокой Y.

Временная сложность: O(N*M*2 N )
Вспомогательное пространство: O(N)

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью динамического программирования. Идея состоит в том, чтобы создать двумерный массив, dp[][] размеров (N + 1)*(M + 1) , а состояние dp[i][j] представляет собой максимальную длину подпоследовательности X[0, i], которая является подстрокой Y[0, j] . Выполните следующие шаги, чтобы решить проблему:

  • Создайте двумерный массив dp[][] размером N+1 строк и M+1 столбцов.
  • Инициализируйте первую строку и первый столбец матрицы с 0 .
  • Заполните все оставшиеся строки следующим образом:
    • Если значение X[i – 1] равно значению Y[j – 1] , тогда обновите значение dp[i][j] до (1 + dp[i – 1][j – 1] ) .
    • В противном случае обновите значение dp[i][j] до dp[i – 1][j] .
  • Сохраните максимальную длину требуемой последовательности в переменной len , перебирая последнюю строку в матрице, и сохраните индекс строки и столбца максимального значения ячейки в переменных i и j соответственно.
  • Создайте переменную, скажем, res , чтобы сохранить результирующую строку и вернуться от максимального значения ячейки.
  • Повторяйте, пока значение len не станет больше 0 , и выполните следующие шаги:
    • Если значение X[i – 1] равно значению Y[j – 1] , тогда добавьте X[i – 1] к res и уменьшите значение len , i и j на 1.
    • В противном случае уменьшите значение i на 1.
  • После выполнения вышеуказанных шагов выведите в качестве результата строку res .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M)
Вспомогательное пространство: O(N*M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ