XOR 최대 timer 2초 memory 1024MB

어떤 문자열에서 연속한 위치에 있는 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)의 최댓값을 구하는 프로그램을 작성하라.