solution

Phương pháp Kasiski Examination dùng để ước lượng độ dài khóa của mật mã Vigenère, dựa trên quan sát: nếu một cụm ký tự trong bản rõ trùng lặp 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ự tương ứng trong bản mã cũng sẽ trùng lặp.

Cụ thể, thực hiện các bước sau trên bản mã:

1. Chuẩn hóa bản mã: chỉ giữ chữ cái $A \ldots Z$, viết hoa, được chuỗi $S$ độ dài $N$.
2. Với mỗi vị trí $i$ từ $0$ đến $N-3$ (đánh số từ 0), xét trigram (chuỗi con độ dài 3) $S[i \ldots i+2]$.
3. Với mỗi giá trị trigram xuất hiện tại từ 2 vị trí trở lên, xét các khoảng cách giữa các lần xuất hiện liên tiếp của trigram đó (vị trí xuất hiện sau trừ vị trí xuất hiện ngay trước, theo thứ tự vị trí tăng dần) — không xét khoảng cách giữa các lần xuất hiện không liền kề nhau.
4. Gộp tất cả các khoảng cách thu được từ mọi trigram (có thể có giá trị trùng nhau) thành một tập hợp (đa tập) các khoảng cách. Tính $g = \gcd$ của toàn bộ các khoảng cách đó.

Nếu không tồn tại trigram nào lặp lại (tập khoảng cách rỗng), in ra undefined. Ngược lại, in ra giá trị $g$ — đây chính là ước lượng độ dài khóa theo phương pháp Kasiski.

Ví dụ: với bản mã ABCXYZABCPQRABC, trigram ABC xuất hiện tại các vị trí $0, 6, 12$. Các khoảng cách liên tiếp là $6-0=6$ và $12-6=6$. Không trigram nào khác lặp lại. Vậy $g = \gcd(6,6) = 6$.