DE
RU
EN
ES
ZH
FR
PT
AR
HI
🎉 Glückwunsch! 🎉
Du hast die Aufgabe hervorragend gelöst! Es war schwierig, aber du hast die Lösung gefunden. Du bist dem Meister einen Schritt näher! Mach weiter so.
Lektion 6. Lists
Schwierigkeit:
Aufgabe«Größte gemeinsame Teilfolge suchen»
💻 Python
Sie entwickeln ein Programm zum Vergleichen von Textdaten und müssen die längste gemeinsame Teilsequenz zwischen zwei Zeilen finden.
Es werden zwei Zeilen gegeben. Finden Sie die längste gemeinsame Teilsequenz (LCS, Longest Common Subsequence).
Eingabeformat
zwei Zeilen, deren Elemente jeweils durch Leerzeichen getrennt sind (wenn das Element eins ist, dann vergleiche es innerhalb)
Ausgabeformat
Die längste allgemeine Teilfolge
Beispiel
Eingabe
Musik Film Reisen Buch Sport
Kino Tanzen Bücher Kulinarik
Ausgabe
Kino Buch
Hinweis
There will be no clue here, decide for yourself!
main.py
Test 1
Test 2
Test 3
Test 4
Test 5
Test 6
Test 7
Test 8
Test 9
Test 10
Entwicklerlösung
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))
