해시 충돌 문자열

다음 프로그램에 문자열 두 개를 입력하면, 두 문자열이 서로 다르면서 hashCode 값이 같을 때만 "true"를 출력한다.

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        if (!a.equals(b) && a.hashCode() == b.hashCode()) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
}

java.lang.String.hashCode는 길이가 $n$인 문자열 $s = s_0 s_1 \dots s_{n-1}$에 대해

$H(s) = s_0 \cdot 31^{n-1} + s_1 \cdot 31^{n-2} + \dots + s_{n-2} \cdot 31 + s_{n-1}$

를 32비트 부호 있는 정수 연산으로 계산한다. 즉 중간 결과는 모두 $2^{32}$로 나눈 나머지를 취해 $-2^{31}$ 이상 $2^{31}-1$ 이하의 값으로 되돌린다. $s_i$는 그 문자의 아스키 코드다.

길이가 $N$이고 영문 대소문자로만 이루어진 서로 다른 문자열 $a$, $b$ 중에서 $H(a) = H(b)$를 만족하는 쌍을 찾아 출력한다.

첫째 줄에 문자열의 길이 $N$ ($2 \le N \le 100$)이 주어진다.

조건을 만족하는 쌍은 여러 가지이므로, 다음 한 쌍만 정답으로 인정한다.

첫째 줄에 문자열 $a$를 출력한다. $a$는 대문자 A $N-1$개 뒤에 소문자 a 하나를 붙인 문자열이다.

둘째 줄에 문자열 $b$를 출력한다. $b$는 대문자 A $N-2$개 뒤에 대문자 B 두 개를 붙인 문자열이다.

두 문자열은 길이가 모두 $N$이고, 서로 다르며, hashCode 값이 같다.

"Aa"와 "BB"의 hashCode는 둘 다 2112다. 길이가 같고 해시가 같은 두 문자열 앞에 같은 문자열을 붙여도 해시는 그대로 같다.