课程 6. Lists

难度：

Pythonlib

任务«搜索最大公共子序列（LCS）»

💻 Python

你正在开发一个用于比较文本数据的程序，需要找出两行文本之间的最长公共子序列。

给定两行文本。找出最长公共子序列（LCS, Longest Common Subsequence）。

输入格式

两行，每行的元素之间用空格分隔（如果只有一个元素，则在其内部进行比较）

输出格式

最长公共子序列

示例

输入

音乐电影旅行书籍体育
电影院舞蹈书籍烹饪

输出

影院书

提示

There will be no clue here, decide for yourself!

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))