문자열 매칭 (대용량)

텍스트 T에서 패턴 P가 몇 번 등장하는지 구하여라. 겹치는 것도 카운트한다. 단순 비교로는 시간 초과가 발생한다.

입력

첫째 줄에 텍스트 T, 둘째 줄에 패턴 P가 주어진다.

• 1 ≤ |P| ≤ |T| ≤ 10^7
• T, P는 소문자 알파벳으로만 구성된다.

출력

P가 T에서 등장하는 횟수를 출력한다.

예제 입력 1

ababcabab
abab

예제 출력 1

2

예제 입력 2

aaaaaa
aa

예제 출력 2

5