비제네르 암호 해독

닉 퓨리는 블랙 위도우와 호크아이가 비제네르 암호(Vigenère cipher)로 비밀 메시지를 주고받고 있다는 사실을 알아내고, 반란이 일어날까 걱정하고 있다. 암호 설명을 읽던 그는 이 암호가 한때 le chiffre indéchiffrable("해독 불가능한 암호")라고 불렸다는 것을 알고 낙담했고, 이제 당신에게 이 암호를 깨는 것을 도와달라고 부탁한다.

계속 읽어 보면 이 암호가 사실은 상당히 취약하다는 것을 알 수 있다. 1846년 찰스 배비지는 훗날 카시스키(Kasiski)가 발표한 기법, 즉 카시스키 검사(Kasiski examination)를 이용해 암호문 표본을 해독했다.

카시스키 검사는 암호문에서 반복되는 문자열을 찾아 키워드의 길이를 추측한다. 예를 들어 다음과 같은 평문, (필요한 만큼 반복한) 키워드, 암호문을 생각하자.

키워드: ABCDABCDABCDABCDABCDABCDABCD
평문:   CRYPTOISSHORTFORCRYPTOGRAPHY
암호문: CSASTPKVSIQUTGQUCSASTPIUAQJB

평문에는 CRYPTO가 반복되며, 두 번의 등장이 반복되는 키워드의 같은 위치와 맞아떨어지기 때문에 둘 다 같은 암호문 CSASTP로 암호화된다. 이렇게 암호문에서 반복되는 부분 문자열을 삼중쌍 $\langle s, p, q\rangle$로 나타낸다. 여기서 $s$는 반복된 문자열이고, $p < q$는 두 등장의 시작 위치(1부터 시작)이다. 위 반복은 $\langle \texttt{CSASTP}, 1, 17\rangle$이고 거리는 $q - p = 16$이다. 키워드 길이는 이 거리의 약수(여기서는 $1, 2, 4, 8, 16$)로 추측한다.

반복되는 문자열이 우연일 수도 있으므로, 추측 알고리즘은 어느 정도의 잡음을 허용해야 한다.

당신의 임무는 주어진 암호문에 대해, 길이가 정확히 3인 반복 문자열만을 이용해 가능한 키워드 길이를 찾는 것이다. 두 번 이상 등장하는 길이 3짜리 문자열을 모두 찾고, 각 문자열에 대해 등장 위치들의 모든 (순서 없는) 쌍이 하나의 삼중쌍을 이룬다. 삼중쌍이 $$\langle s_1, p_1, q_1\rangle, \langle s_2, p_2, q_2\rangle, \dots, \langle s_n, p_n, q_n\rangle$$ 이고 거리가 $x_i = q_i - p_i$라고 하자. 어떤 수 $k$가 거리 집합 ${x_1, \dots, x_n}$의 90% 이상을 나누어떨어뜨릴 때, 그리고 오직 그때에만 $k$를 키워드 길이의 추측값으로 삼는다. 단 $4 \le k \le 20$인 $k$만 고려한다. 반복되는 삼중쌍이 하나도 없으면(거리 집합이 비어 있으면) 추측값은 없다.

겹치는 문자열도 각각 따로 센다. 이렇게 하면 더 긴 반복에 자연스럽게 더 큰 가중치가 주어진다. 예를 들어 암호문 VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR에는 길이 4인 반복이 두 개 있고, 이로부터 길이 3인 반복 네 개 VHV, HVS, QUC, UCE가 나온다(VHV와 HVS는 겹치지만 따로 센다). 이들의 거리는 각각 $18, 18, 30, 30$이며, 이 중 90% 이상을 나누는 4 이상 20 이하의 키워드 길이는 $6$뿐이다.

첫 줄에는 테스트 케이스의 수 $T$가 주어진다($T < 100$). 이어지는 $T$개의 줄에는 각각 하나의 테스트 케이스, 즉 암호문 문자열이 하나씩 주어진다. 암호문은 대문자 A–Z로만 이루어져 있으며, 모든 숫자·문장 부호·공백은 이미 제거되어 있다.

각 테스트 케이스에 대해 4 이상 20 이하의 키워드 길이 추측값을 출력한다. 추측값이 하나 이상 있으면 Possible key lengths between 4 and 20:을 출력한 뒤 공백 하나를 두고 추측값들을 오름차순으로 공백 하나씩 구분하여 출력한다. 추측값이 없으면 대신 No guesses found.를 출력한다.