D. Ikki qadimiy bitik
Vaqt limiti: 2000 ms Xotira limiti: 256 mb
Yosh arxeolog Laylo ikkita turli qazishma hududidan topilgan qadimgiy bitiklarni (yozuvlarni) tekshirmoqda. Ikkala bitik ham faqat kichik lotin harflaridan iborat maxsus belgilar tizimida bitilgan. Agar bu ikki bitikda bir xil tartibda ketma-ket takrorlanadigan yetarlicha uzun umumiy parcha topilsa, bu ular bir xil qadimiy sivilizatsiyaga tegishli ekanligidan dalolat beradi.
Laylaga yordam bering: ikkita \(s\) (uzunligi \(n\)) va \(t\) (uzunligi \(m\)) bitik matni berilgan. Ikkalasida ham birgalikda uchraydigan eng uzun umumiy qism-satr (ketma-ket parcha)ning uzunligini toping. Agar umuman umumiy parcha (bo'sh bo'lmagan) topilmasa, \(0\) chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son \(n\), \(m\) (\(1 \le n, m \le 2 \times 10^5\)) — bitiklar uzunligi. Ikkinchi qatorda birinchi bitik matni \(s\), uchinchi qatorda ikkinchi bitik matni \(t\) beriladi.
Chiquvchi ma'lumotlar
Yagona qatorda — eng uzun umumiy qism-satr uzunligini chiqaring.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
8 6 ababbabc bbabbc |
4 |
2 |
3 3 abc xyz |
0 |
3 |
4 4 aaaa aaaa |
4 |