सबसे लंबा सामान्य उपक्रम (Longest Common Subsequence)
आपको दो अनुक्रम a और b दिए गए हैं, जिनकी लंबाई क्रमशः n और m है। आपका कार्य इन दोनों अनुक्रमों का सबसे लंबा सामान्य उपक्रम (Longest Common 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