सबसे लंबा सामान्य उपक्रम (Longest Common Subsequence)
आपको दो अनुक्रम
a और b दिए गए हैं, जिनकी लंबाई क्रमशः n और m है। आपका कार्य इन दोनों अनुक्रमों का सबसे लंबा सामान्य उपक्रम (Longest Common Subsequence) ढूँढना है, और उसकी लंबाई निकालनी है।💡
एक उपक्रम (subsequence) वह नया अनुक्रम होता है, जिसे मूल अनुक्रम से कुछ (या कोई भी नहीं) तत्त्व हटाकर बनाया जाता है, लेकिन शेष तत्त्वों के क्रम में कोई बदलाव नहीं किया जाता।
इनपुट
इनपुट की पहली पंक्ति में दो रिक्त-स्थानों से अलग किए गए पूर्णांक
n और m होते हैं (1 ≤ n, m ≤ 1000)।
दूसरी पंक्ति में n पूर्णांक होते हैं, जो अनुक्रम a के तत्त्वों का प्रतिनिधित्व करते हैं (1 ≤ ≤ )।
तीसरी पंक्ति में m पूर्णांक होते हैं, जो अनुक्रम b के तत्त्वों का प्रतिनिधित्व करते हैं (1 ≤ ≤ )।आउटपुट
एक अकेला पूर्णांक प्रिंट करें, जो
a और b के सबसे लंबा सामान्य उपक्रम (Longest Common Subsequence) की लंबाई दर्शाता है।उदाहरण
इनपुट | आउटपुट |
5 4
2 1 5 3 4
2 5 1 4 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB