Найти самую длинную подпоследовательность строки, которая является подстрокой другой строки
Даны две строки 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)