ES
RU
EN
ZH
FR
DE
PT
AR
HI
🎉 ¡Felicidades! 🎉
¡Has resuelto la tarea brillantemente! Era un reto difícil, pero encontraste la solución correcta. ¡Estás un paso más cerca de dominar la programación! Sigue así, cada etapa superada te hace más fuerte.
Lección 6. Lists
Dificultad:
Tarea«Buscar subsecuencia común máxima»
💻 Python
Estás desarrollando un programa para comparar datos de texto y necesitas encontrar la subsecuencia común más larga entre dos líneas.
Se dan dos líneas. Encuentra la subsecuencia común más larga (LCS, Longest Common Subsequence).
Formato de entrada
dos líneas, cuyos elementos están separados por espacios (si el elemento es uno, entonces compare dentro de él)
Formato de salida
La subsecuencia general más larga
Ejemplo
Entrada
Música Cine Viajes Libros Deportes
Cine Baile Libros Culinaria
Salida
Cinema Book
Pista
There will be no clue here, decide for yourself!
main.py
Prueba 1
Prueba 2
Prueba 3
Prueba 4
Prueba 5
Prueba 6
Prueba 7
Prueba 8
Prueba 9
Prueba 10
Solución del desarrollador
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))
