RU
EN
RU
EN
🎉 Поздравляем! 🎉
Ты отлично справился с задачей! Это был непростой вызов, но ты нашёл правильное решение. Ты на шаг ближе к мастерству в программировании! Продолжай в том же духе, ведь каждый пройденный этап делает тебя ещё сильнее.
Занятие 6. Списки
Уровень сложности:
Задача«Поиск (LCS)»
Вы разрабатываете программу для сравнения текстовых данных и вам нужно найти наибольшую общую подпоследовательность между двумя строками.
Даны две строки. Найдите наибольшую общую подпоследовательность (LCS, Longest Common Subsequence).
Формат ввода
Две строки, подстроки каждой из которых разделены пробелами (если элемент один, то сравнивать внутри него)
Формат Вывода
Самая длинная общая подпоследовательность
Пример
Ввод
музыка кино путешествия книги спорт
кино танцы книги кулинария
Вывод
кино книги
Подсказка
Тут подсказки не будет, решай сам!
main.py
Тест 1
Тест 2
Тест 3
Тест 4
Тест 5
Тест 6
Тест 7
Тест 8
Тест 9
Тест 10
Решение разработчика
def longest_common_subsequence(s1, s2):
"""
Находит самую длинную общую подпоследовательность между двумя строками.
Работает как пословно, так и посимвольно — автоматически.
"""
# Если строки содержат пробелы — считаем, что нужно сравнивать слова
if ' ' in s1 or ' ' in s2:
seq1 = s1.split()
seq2 = s2.split()
join_result = lambda lst: ' '.join(lst) # итог как строка слов
else:
seq1 = list(s1)
seq2 = list(s2)
join_result = lambda lst: ''.join(lst) # итог как строка символов
n, m = len(seq1), len(seq2)
# Матрица DP для хранения последовательностей
dp = [[""] * (m + 1) for _ in range(n + 1)]
# Заполнение таблицы
for i in range(n):
for j in range(m):
if seq1[i] == seq2[j]:
dp[i + 1][j + 1] = dp[i][j] + " " + seq1[i]
else:
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], key=len)
# Возвращаем результат без лишнего пробела
return join_result(dp[-1][-1].strip().split())
# === Точка входа ===
if __name__ == "__main__":
s1 = input()
s2 = input()
print(longest_common_subsequence(s1, s2))
