لتكن لدينا كلمة $w$، وهي سلسلة من $n$ أحرف إنجليزية صغيرة. لموضعين معطيين، أي عددين صحيحين موجبين $a$ و$b$ يحققان $1 \le a \le b \le n$، نعرّف السلسلة الفرعية $w_{a,b}$ بأنها الكلمة الناتجة عن أخذ جميع المحارف بالترتيب من الموضع $a$ حتى الموضع $b$ في الكلمة $w$. ونعرّف أيضًا الباقي $o_{a,b}$ بأنه الكلمة الناتجة عن حذف جميع المحارف من الموضع $a$ حتى الموضع $b$ من الكلمة $w$.
أوجد طول أطول سلسلة فرعية $w_{a,b}$ بحيث يحتوي الباقي $o_{a,b}$ أيضًا على $w_{a,b}$ كسلسلة فرعية.
الإدخال
يحتوي السطر الأول على الكلمة المعطاة $w$، وهي سلسلة من أحرف إنجليزية صغيرة.
الإخراج
اطبع أكبر طول ممكن مطلوب.
المهام الفرعية
ليكن $n$ طول الكلمة المعطاة.
| المهمة الفرعية | النقاط | القيود |
|---|---|---|
| $1$ | $16$ | $1 \le n \le 400$ |
| $2$ | $24$ | $401 \le n \le 5\,000$ |
| $3$ | $60$ | $5001 \le n \le 100\,000$ |
أمثلة
الإدخال 1
abcxyzabc
الإخراج 1
3
الإدخال 2
bbcdbcbbcbadadda
الإخراج 2
5
ملاحظة
شرح المثال الثاني: bbcdbcbbcbadadda $\to$ bbcdbcbadda