Oulipo

프랑스 작가 조르주 페렉(1936-1982)은 알파벳 'e'를 한 번도 쓰지 않고 소설 《La disparition》을 완성했다. 페렉은 울리포(Oulipo) 모임의 일원이었다. 소설의 한 대목이다.

Tout avait l’air normal, mais tout s’affirmait faux. Tout avait l’air normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : sur son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…

페렉이라면 아래 대회에서 아주 높은 점수, 정확히 말하면 아주 낮은 점수를 받았을 것이다. 참가자는 주어진 주제로 글을 쓰되 지정된 단어 하나가 최대한 적게 나오도록 써야 한다. 심사위원단은 그 단어가 몇 번 나오는지 세어 순위를 정할 프로그램이 필요하다. 참가자가 뜻이 전혀 없는 아주 긴 글을 내는 일도 흔하다. 'T'가 500,000번 연달아 이어지는 글도 드물지 않고, 공백은 절대 쓰지 않는다.

그래서 한 문자열이 다른 문자열 안에 몇 번 나오는지 빠르게 세야 한다. 알파벳 {'A', 'B', 'C', …, 'Z'}로 이루어진 단어 $W$와 텍스트 $T$가 주어진다. $T$ 안에 $W$가 나타나는 횟수를 구하라. $W$의 모든 문자가 $T$의 연속한 문자와 정확히 일치해야 한다. 나타나는 위치는 서로 겹쳐도 된다.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫째 줄에 단어 $W$가 주어진다. $W$는 {'A', 'B', 'C', …, 'Z'}로 이루어진 문자열이고 $1 \le |W| \le 10^4$이다. 여기서 $|W|$는 $W$의 길이를 뜻한다.
• 둘째 줄에 텍스트 $T$가 주어진다. $T$는 같은 알파벳으로 이루어진 문자열이고 $|W| \le |T| \le 10^6$이다.

각 테스트 케이스마다 $T$ 안에 $W$가 나타나는 횟수를 한 줄에 하나씩 출력한다.