Courses

thuật toán

băm

Module: băm

Problem

6 /8

Huckleberry Finn và hai sợi dây

Theory Click to read/hide

Nếu chúng ta có hàm băm của chuỗi A bằng h_A và hàm băm của chuỗi B bằng h_B, thì chúng ta có thể tính nhanh hàm băm của chuỗi AB:
h_AB = h_A * p^|B| + h_B <- đếm mọi thứ theo modulo
nơi |B| - chiều dài của chuỗi B.

Problem

Huckleberry Finn có hai xâu s và t có cùng độ dài n.
Huckleberry Finn thích các chuỗi có cùng tiền tố (bắt đầu), vì vậy anh ấy có thể hoán đổi hai ký tự trong chuỗi s để tạo tiền tố chung của chuỗi s và t lớn hơn.
Tuy nhiên, thủ thuật này khá tẻ nhạt, vì vậy Huckleberry Finn sẽ không thực hiện hoặc sẽ thực hiện chính xác một lần.

Hãy giúp Huckleberry Finn xác định độ dài tiền tố chung dài nhất của chuỗi s và t mà cậu ấy có thể nhận được.

Đầu vào:
Dòng đầu tiên chứa số tự nhiên n (1 <= n <= 200000) - độ dài của xâu s và t
Dòng thứ hai chứa một xâu s gồm các chữ cái Latinh viết thường.
Dòng thứ ba chứa một xâu t bao gồm các chữ cái Latinh viết thường.

Đầu ra:
In ra một số tự nhiên - độ dài tối đa của tiền tố chung s và t, có thể nhận được bằng cách hoán đổi hai ký tự trong chuỗi s nhiều nhất một lần.

Ví dụ:

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