PT
RU
EN
ES
ZH
FR
DE
AR
HI
🎉 Parabéns! 🎉
Você resolveu a tarefa brilhantemente! Foi difícil, mas você encontrou a solução certa. Você está um passo mais perto de dominar a programação! Continue assim.
Lição 6. Lists
Dificuldade:
Tarefa«Buscar maior subsequência comum»
💻 Python
Você está desenvolvendo um programa para comparar dados de texto e precisa encontrar a maior subsequência comum entre duas linhas.
Duas linhas são fornecidas. Encontre a maior subsequência comum (LCS, Longest Common Subsequence).
Formato de entrada
duas linhas, cujos elementos são separados por espaços (se o elemento for um, então compare dentro dele)
Formato de saída
A subsequência geral mais longa
Exemplo
Entrada
Música Filme Viajar Livro Esportes
Cinema Dança Livros Culinária
Saída
Cinema Book
Dica
There will be no clue here, decide for yourself!
main.py
Teste 1
Teste 2
Teste 3
Teste 4
Teste 5
Teste 6
Teste 7
Teste 8
Teste 9
Teste 10
Solução do desenvolvedor
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))
