25456번 - 궁금한 시프트

문제

시프트는 두 문자열 $S,ドル $T$를 생일 선물로 받았다. 두 문자열의 길이는 $N$이고, '0' 과 '1'로만 이루어져 있다. 두 문자열을 가지고 무엇을 할 수 있을지 고민하던 중 아래 소스 코드도 선물로 받았다.

int calc(string S, string T, int s, int t) {
 int n = S.length();
 int i = s;
 int j = t;
 int cnt = 0;
 for (int k=0; k<n; k++) {
 if (S[i] == '1' && T[j] == '1') {
 cnt += 1;
 }
 i = (i+1) % n;
 j = (j+1) % n;
 }
 return cnt;
}

calc의 S와 T는 문자열 $S$와 $T$이고, s와 t는 0ドル ≤$ s $< N,ドル 0ドル ≤$ t $< N$을 만족해야 한다. 따라서, calc를 호출할 수 있는 방법은 $N^2$개가 있다. 두 문자열 $S$와 $T$가 주어졌을 때, 가능한 calc의 리턴값 중 최댓값을 구해보자.

입력

첫째 줄에 문자열 $S,ドル 둘째 줄에 문자열 $T$가 주어진다.

출력

가능한 calc의 리턴값 중 최댓값을 첫째 줄에 출력한다.

제한

• 1ドル ≤ N ≤ 500,000円$

힌트