solution

Phương pháp Kasiski là kỹ thuật thám mã cổ điển dùng để ước lượng độ dài khóa của một bản mã Vigenère, dựa trên quan sát: nếu một cụm 3 ký tự liên tiếp trong bản rõ bị lặp lại và khoảng cách giữa hai lần xuất hiện là bội số của độ dài khóa, thì cụm ký tự mã hóa tương ứng trong bản mã cũng sẽ trùng lặp.

Cho bản mã $C$ (chữ in hoa A-Z, không khoảng trắng, có thể rỗng). Hãy thực hiện thuật toán Kasiski sau đây để ước lượng độ dài khóa:

1. Xét tất cả các cụm con liên tiếp có độ dài đúng bằng 3 ký tự (gọi là tam đồ, trigram) xuất hiện trong $C$, tại mọi vị trí bắt đầu có thể (đánh số vị trí từ 0).
2. Với mỗi giá trị tam đồ xuất hiện từ 2 lần trở lên, sắp xếp các vị trí xuất hiện của nó tăng dần, rồi tính khoảng cách giữa các lần xuất hiện liên tiếp (vị trí sau trừ vị trí ngay trước nó trong danh sách đã sắp xếp).
3. Gộp tất cả các khoảng cách thu được từ mọi tam đồ lặp lại vào một danh sách chung.
4. Kết quả cần in ra là ước chung lớn nhất (GCD) của toàn bộ các khoảng cách trong danh sách đó.

Nếu không có tam đồ nào lặp lại (kể cả trường hợp $|C| < 3$), in ra 0.

Ví dụ: $C=$ ACEACEACEACEACEACEACEACEACEACE (chu kỳ lặp rõ ràng là 3 — các tam đồ ACE, CEA, EAC đều lặp lại đều đặn với khoảng cách 3) → in ra 3.