تقاطع أصغر الإزاحات الدورية

C++ Hard strings

مهمة «تقاطع أصغر الإزاحات الدورية»

تم إعطاء سلسلتين نصيتين <code>s</code> و <code>t</code>، تتكونان من أحرف لاتينية صغيرة. المطلوب إيجاد طول أطول سلسلة فرعية مشتركة، والتي تكون سلسلة فرعية من بعض الإزاحة الدائرية للسلسلة <code>s</code> وبعض الإزاحة الدائرية للسلسلة <code>t</code>. الإزاحة الدائرية هي إعادة ترتيب لأحرف السلسلة، حيث يتم إزاحة جميع الأحرف بمقدار <code>k</code> موضعًا إلى اليسار، وتُنقل الأحرف التي تسقط من اليسار إلى النهاية. لا يتجاوز طول السلسلتين <code>10^5</code>. إذا لم يتم العثور على سلسلة فرعية مشتركة، يتم إخراج <code>0</code>.

تنسيق الإدخال

في السطر الأول، تُعطى السلسلة s (1 ≤ |s| ≤ 10^5). في السطر الثاني، تُعطى السلسلة t (1 ≤ |t| ≤ 10^5). تتكون السلاسل فقط من أحرف لاتينية صغيرة.

تنسيق الإخراج

أخرج عددًا صحيحًا واحدًا — طول أطول سلسلة فرعية مشتركة تظهر في بعض الإزاحة الدائرية لـ s وبعض الإزاحة الدائرية لـ t.

أمثلة

مثال 1

الإدخال

abc
def

الإخراج

0

مثال 2

الإدخال

bcd

الإخراج

abc

main.cpp