(matkhauqt.*)

Lan thường đặt mật khẩu các tệp dữ liệu quan trọng. Mỗi khi gửi những tệp này cho thư ký tổng hợp, Lan chỉ gửi một chuỗi \(s\) và nhắn mật khẩu mở tệp là số lượng kí tự xuất hiện nhiều nhất trong ước của chuỗi \(s\).

Chuỗi \(x\) được gọi là ước của chuỗi \(s\) nếu chuỗi \(x\) có độ dài ngắn nhất và khi ghép một số lần liên tiếp chuỗi \(x\) ta được chuỗi \(s\). Ví dụ:

• \(s = \ ‘aaaaa’\) có ước là \(x = \ ‘a’\);

• \(s\ = \ ‘abc’\) có ước là \(x\ = \ ‘abc’;\)

• \(s\ = \ ‘ababab’\) có ước là \(x\ = \ ‘ab’\).

Yêu cầu: Cho một chuỗi kí tự \(s\), hãy giúp thư ký tìm ra mật khẩu mở tệp.

Dữ liệu vào:

+ Chỉ có một dòng duy nhất ghi chuỗi kí tự \(s\) gồm các chữ cái thường.

Kết quả:

+ Ghi một số nguyên duy nhất là mật khẩu cần tìm.

Ví dụ:

Ràng buộc:

+ Có 60% số điểm tương ứng với: Chuỗi \(s\) có độ dài không quá 255;

+ Có 40% số điểm tương ứng với: Chuỗi \(s\) có độ dài không quá 5000.