유전자 검색

지난 10년 동안 생물학 분야는 크게 바뀌었다. 생물학적 정보를 디지털화하여 컴퓨터로 분석할 수 있게 되었기 때문이다. 가장 기본적인 분석 작업 중 하나는 검색 문자열 $S$가 $S$ 이상의 길이를 가진 다른 문자열 $L$ 안에서 몇 번 나타나는지(또는 거의 나타나는지) 세는 것이다.

이 문제에서는 문자열 쌍 $S$와 $L$이 주어진다. 두 문자열은 모두 대문자 A, G, C, T로만 이루어져 있다. 다음 각 유형의 검색 문자열에 대해, 그 유형이 $L$의 정확한 부분 문자열로 나타나는 횟수를 세어라.

• 유형 1: 아무런 변경도 하지 않은 $S$.
• 유형 2: $S$에서 문자 하나를 삭제하여 만들 수 있는 모든 서로 다른 문자열 (예를 들어 AGC는 AG, AC, GC가 될 수 있다).
• 유형 3: $S$에 문자 하나를 삽입하여 만들 수 있는 모든 서로 다른 문자열 (예를 들어 AG는 AAG, GAG, CAG, TAG, AGG, ACG, ATG, AGA, AGC, AGT가 될 수 있다).

$S$를 서로 다르게 변형한 결과가 같은 문자열이 되면, 그 문자열이 나타나는 횟수는 한 번만 센다.

입력 파일은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 두 문자열 $S$와 $L$을 포함한다. $S$의 길이는 2 이상이고 $L$의 길이 이하이다. $L$의 길이는 100 이하이다. 마지막 테스트 케이스 다음에는 0 하나만 있는 줄이 온다.

각 테스트 케이스마다 케이스 번호(1부터 시작)를 출력하고, 그 뒤에 유형 1, 유형 2, 유형 3이 나타나는 횟수를 차례로 출력한다.