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$