순환 순열

면접 대비

시간 제한2초메모리 제한512 MB

요약

이진 문자열 B를 왼쪽으로 회전시켜 이진 문자열 A와 같아지는 경우의 수를 셉니다.

난이도: 보통10점 중 4점
유형: 문자열 매칭
정답자: 아직 제출이 없습니다

문제

두 이진 문자열 $A$ 와 $B$ 가 주어진다. $B$ 를 왼쪽으로 순환 이동시킨 문자열 중에서 $A$ 와 비트 단위 XOR을 했을 때 모든 자리가 0이 되는 것이 몇 개인지 세는 프로그램을 작성하시오.

길이가 $N$ 인 문자열 $P = P_0 P_1 \dots P_{N-1}$ 을 왼쪽으로 $k$ 번 순환 이동시킨 문자열은 $i$ 번째 자리가 $P_{(i+k) \bmod N}$ 인 문자열이다. 이동 횟수 $k$ 는 $0 \le k < N$ 인 정수이고, $k$ 가 다르면 결과 문자열이 같더라도 서로 다른 순환 이동으로 센다.

입력

첫째 줄에 $A$ , 둘째 줄에 $B$ 가 주어진다. 두 문자열은 0과 1로만 이루어져 있고 길이가 서로 같으며, 그 길이는 1 이상 $10^5$ 이하이다.

출력

첫째 줄에 $A$ 와 XOR한 결과가 모두 0이 되는 $B$ 의 순환 이동의 개수를 출력한다.

예제2

예제 1
입력
```
101
101
```
예상 출력
```
1
```
예제 2
입력
```
111
111
```
예상 출력
```
3
```