어떤 문자열에서 연속한 위치에 있는 1개 이상의 문자를 선택해 순서를 유지한 채로 나열해서 얻을 수 있는 문자열을 그 문자열의 부분문자열이라 한다. 예를 들어, \(001\)는 \(X = 1\underline{001}1\)의 부분문자열이지만, \(Y = 10101\)의 부분문자열은 아니다.

음이 아닌 두 정수 \(A, B\)의 배타적 논리합 \(A \oplus B\)는 다음과 같이 정의된다.

• 이진법으로 생각했을 때, \(A\)의 \(2^k\)의 자릿수와 \(B\)의 \(2^k\)의 자릿수가 서로 다르면 \(A \oplus B\)의 \(2^k\)의 자릿수가 \(1\)이고, 같으면 \(A \oplus B\)의 \(2^k\)의 자릿수가 \(0\)이다. (단, \(k \ge 0\))
• 예를 들어 \(12 \oplus 10\)은 \(12 = 1100_{(2)}, 10 = 1010_{(2)}\)이므로 \(1100_{(2)} \oplus 1010_{(2)} = 0110_{(2)} = 6\)이다.

\(0\)과 \(1\)로만 구성된 길이가 \(N\)인 문자열 \(S\)가 주어진다.

당신은 \(S\)의 부분문자열 \(s_1, s_2\)를 선택해서 만들 수 있는 \(g(s_1, s_2)\)의 최댓값을 계산해야 한다. \(g(s_1, s_2)\)는 다음과 같이 정의되는 함수이다:

• \(S\)의 부분문자열 \(s\)에 대해, \(f(s)\)의 값은 \(s\)를 이진법으로 해석했을 때의 값이다. 예를 들어, 만약 \(s = 11010\)이면 \(f(s) = 26\)이다.
• \(g(s_1, s_2)\)는 \(f(s_1)\)과 \(f(s_2)\)의 배타적 논리합이다.

이때 \(s_1\)과 \(s_2\)가 서로 다를 필요는 없다. 즉, \(s_1\)과 \(s_2\)는 \(S\)에서 일부가 겹쳐도 되고, 완전히 같은 문자열이어도 된다.

\(0\)과 \(1\)로만 구성된 문자열 \(S\)가 주어지면, 가능한 \(g(s_1, s_2)\)의 최댓값을 구하는 프로그램을 작성하라.

• 주어지는 모든 수는 정수이다.
• \(1 \le T \le 100\)
• \(2 \le N \le 10^7\)
• 모든 테스트 케이스에서 \(N\)의 합 \(\le 10^7\)
• \(S\)는 \(0\)과 \(1\)로만 이루어진 길이가 \(N\)인 문자열이다.

첫 번째 줄에 테스트 케이스의 개수 \(T\)가 주어진다.

각 테스트 케이스마다, 첫 번째 줄에 문자열의 길이 \(N\), 두 번째 줄에 \(0\)과 \(1\)로만 구성된 길이가 \(N\)인 문자열 \(S\)가 주어진다.

각 테스트 케이스마다 가능한 \(g(s_1, s_2)\)의 최댓값을 이진법으로 한 줄에 하나씩 출력한다. 단, 정답 앞에 필요 없는 \(0\)은 출력하지 않는다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2024 > 2차 대회 > 중등부 3번 / 고등부 2번