원피스

지금은 대해적 시대다. 밀짚모자 해적단의 선장 교정이는 어린 시절에 잊지 못할 한마디를 들었다. 해적 왕 골.D.상윤이 자신이 모은 모든 보물인 원피스를 위대한 항로에 두고 왔다는 얘기였다. 원피스를 손에 넣은 자가 이 세상을 가진다는, 매혹적인 얘기이기도 했다.

모두 말도 안 된다며 고개를 저었지만 교정이는 동료를 모아 원피스를 찾는 여행을 떠났다. 하늘섬과 어인섬을 지나고 사황을 무너뜨린 끝에 교정이와 동료들은 원피스의 위치가 적힌 결정적인 단서를 찾아냈다. 단서는 한눈에 해독하기 어려웠다. 알파벳 대문자만 빈틈없이 이어져 있었기 때문이다.

천재적인 두뇌를 가진 항해사 진아는 이 단서에 어떤 문자열이 여러 번 등장한다고 단번에 직감했다. 그 문자열이 무엇인지는 알 수 없었으므로, 진아는 자신이 떠올린 문자열이 단서 전체에 몇 번 나오는지부터 세어 보기로 했다. 가장 많이 나온 문자열이 원피스의 위치를 알려 줄 것이라고 생각했기 때문이다.

진아가 해적단의 프로그래밍 담당인 당신에게 도움을 요청했다. 단서 $H$ 안에 진아가 고른 문자열 $N$이 몇 번 등장하는지 세는 프로그램을 작성하라.

첫째 줄에 해적단이 얻은 단서 문자열 $H$가 주어진다. ($0 < |H| \le 100\,000$)

둘째 줄에 진아가 등장 횟수를 알고 싶은 문자열 $N$이 주어진다. ($0 < |N| \le 10$)

$H$와 $N$은 공백이 없는 문자열이며, 알파벳 대문자로만 이루어져 있다.

$H$ 안에 $N$이 몇 번 등장하는지 한 줄에 출력한다. 서로 겹쳐서 등장하는 경우도 각각 센다. $H$가 AAAA이고 $N$이 AA이면 답은 3이다.