Problem

6 /8


Huckleberry Finn وخيطين

Theory Click to read/hide

إذا كان لدينا تجزئة السلسلة A تساوي h A & nbsp ؛ وتجزئة السلسلة B تساوي h B ، فيمكننا حساب تجزئة السلسلة AB بسرعة:
h AB & nbsp؛ = h A & nbsp؛ * p | B | & nbsp؛ + h B & nbsp؛ على & nbsp ؛ العلامة & lt ؛ - عد كل شيء modulo
حيث | ب | - طول الخيط ب.

Problem

يحتوي Huckleberry Finn على سلسلتين s و t لهما نفس الطول n.
يحب Huckleberry Finn أن تحتوي السلاسل على نفس البادئات (البدايات) ، لذلك يمكنه تبديل حرفين في سلسلة s لجعل البادئة المشتركة بين السلاسل s و t أكبر.
ومع ذلك ، فإن هذه الحيلة مملة نوعًا ما ، لذا فإن Huckleberry Finn إما لن يفعلها على الإطلاق ، أو سيفعلها مرة واحدة بالضبط.

ساعد Huckleberry Finn في تحديد أطول طول بادئة مشتركة من السلاسل s و t يمكنه الحصول عليها.


الإدخال:
يحتوي السطر الأول على عدد طبيعي n (1 & lt؛ = n & lt؛ = 200000) - طول السلاسل s و t
يحتوي السطر الثاني على سلسلة تتكون من أحرف لاتينية صغيرة.
السطر الثالث يحتوي على سلسلة t تتكون من أحرف لاتينية صغيرة.

الإخراج:
اطبع رقمًا طبيعيًا واحدًا - الحد الأقصى لطول البادئة المشتركة s و t ، والذي يمكن الحصول عليه من خلال تبادل حرفين في السلسلة s مرة واحدة على الأكثر.

أمثلة:
نبسب ؛ <الجسم>
إدخال الإخراج
3
واي
add 		1
5
qdyid
xreac 		0

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!