Courses

algoritmalar

karma

Module: karma

Problem

6 /8

Huckleberry Finn ve iki tel

Theory Click to read/hide

A dizesinin h_A 'ya eşit bir hash'i ve B dizesinin h_B'ye eşit bir hash'i varsa, o zaman AB dizesinin hash'ini hızlıca hesaplayabiliriz:
h_AB = h_A * p^|B| + h_B <- her şeyi sayma modulo
nerede |B| - B dizisinin uzunluğu.

Problem

Huckleberry Finn'in s ve t olmak üzere aynı uzunlukta n olmak üzere iki dizisi vardır.
Huckleberry Finn, dizelerin aynı öneklere (başlangıçlara) sahip olmasını sever, bu nedenle s ve t dizelerinin ortak önekini büyütmek için s dizisindeki iki karakteri değiştirebilir.
Ancak bu numara oldukça can sıkıcı olduğundan Huckleberry Finn bunu ya hiç yapmayacak ya da tam olarak bir kez yapacak.

Huckleberry Finn'in s ve t dizelerinin alabileceği en uzun ortak önek uzunluğunu belirlemesine yardım edin.

Giriş:
İlk satır bir doğal sayı n (1 <= n <= 200000) içerir - s ve t dizilerinin uzunluğu
İkinci satır, küçük Latin harflerinden oluşan bir s dizisi içerir.
Üçüncü satır, küçük Latin harflerinden oluşan bir t dizisi içerir.

Çıktı:
Bir doğal sayı yazdır - s ve t ortak öneklerinin maksimum uzunluğu, s dizisindeki iki karakterin en fazla bir kez değiş tokuş edilmesiyle elde edilebilir.

Örnekler:

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