HI
RU
EN
ES
ZH
FR
DE
PT
AR
🎉 बधाई! 🎉
आपने कार्य को शानदार ढंग से हल किया! यह कठिन था, लेकिन आपने सही उत्तर खोजा। आप प्रोग्रामिंग में महारत के करीब हैं! ऐसे ही जारी रखें।
पाठ 6. Lists
कठिनाई:
कार्य«सबसे बड़ी सामान्य अनुवर्ती»
💻 Python
आप टेक्स्ट डेटा की तुलना करने के लिए एक प्रोग्राम विकसित कर रहे हैं और आपको दो पंक्तियों के बीच सबसे बड़ी सामान्य अनुक्रम (greatest general subsequence) खोजने की आवश्यकता है।
दो पंक्तियाँ दी गई हैं। सबसे बड़ी सामान्य अनुक्रम (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))
