Courses

Algoritma

Hashing

Module: Hashing

Problem

6 /8

Huckleberry Finn dan dua tali

Theory Click to read/hide

Jika kita mempunyai cincang rentetan A bersamaan dengan h_A dan cincang rentetan B sama dengan h_B, maka kami boleh mengira cincang rentetan AB dengan cepat:
h_AB = h_A * p^|B| + h_B <- mengira semua modulo
di mana |B| - panjang tali B.

Problem

Huckleberry Finn mempunyai dua tali s dan t yang sama panjang n.
Huckleberry Finn suka rentetan mempunyai awalan yang sama (permulaan), jadi dia boleh menukar dua aksara dalam rentetan s untuk menjadikan awalan biasa rentetan s dan t lebih besar.
Walau bagaimanapun, helah ini agak membosankan, jadi Huckleberry Finn sama ada tidak akan melakukannya sama sekali, atau akan melakukannya sekali sahaja.

Bantu Huckleberry Finn menentukan panjang awalan biasa terpanjang rentetan s dan t yang dia boleh dapatkan.

Input:
Baris pertama mengandungi nombor asli n (1 <= n <= 200000) - panjang rentetan s dan t
Baris kedua mengandungi rentetan s, yang terdiri daripada huruf Latin huruf kecil.
Baris ketiga mengandungi rentetan t yang terdiri daripada huruf Latin huruf kecil.

Output:
Cetak satu nombor asli - panjang maksimum awalan biasa s dan t, yang boleh diperoleh dengan menukar dua aksara dalam rentetan s paling banyak sekali.

Contoh:

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