Нахождение максимальной общей подпоследовательности python
- User
Нахождение максимальной общей подпоследовательности python
- Assistant
Максимальная общая подпоследовательность (Longest Common Subsequence, LCS) - это последовательность элементов, которая является подпоследовательностью для двух или более заданных последовательностей, при этом общая подпоследовательность должна быть наибольшей по длине.
В Python есть несколько способов реализации данной задачи. Один из них - это использование динамического программирования с помощью двумерного массива.
Вот пример кода, реализующего нахождение максимальной общей подпоследовательности:
def lcs(seq1, seq2): m = len(seq1) n = len(seq2) dp = [[0] * (n + 1) for _ in range(m + 1)] # Инициализация двумерного массива for i in range(1, m + 1): for j in range(1, n + 1): if seq1[i - 1] == seq2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # Восстановление максимальной общей подпоследовательности result = [] i, j = m, n while i > 0 and j > 0: if seq1[i - 1] == seq2[j - 1]: result.append(seq1[i - 1]) i -= 1 j -= 1 elif dp[i - 1][j] > dp[i][j - 1]: i -= 1 else: j -= 1 result.reverse() return result # Пример использования seq1 = "ABCDGH" seq2 = "AEDFHR" print("Максимальная общая подпоследовательность:", "".join(lcs(seq1, seq2)))В этом примере используется двумерный массив
dp, гдеdp[i][j]представляет длину максимальной общей подпоследовательности дляseq1[:i]иseq2[:j]. Значениеdp[i][j]зависит от(i-1, j-1),(i-1, j)и(i, j-1)и может быть вычислено с помощью формулы:dp[i][j] = dp[i-1][j-1] + 1, если seq1[i-1] == seq2[j-1] dp[i][j] = max(dp[i-1][j], dp[i][j-1]), если seq1[i-1] != seq2[j-1]После нахождения максимальной длины для каждой подпоследовательности, мы используем движение назад по массиву
dp, чтобы восстановить саму максимальную общую подпоследовательность. - User
он выдаст при этом ADН, верно?
- Assistant
Нет, код выше найдет и выведет "ADH" как максимальную общую подпоследовательность для строк "ABCDGH" и "AEDFHR".