Genetic Search

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

요약

각 문자열 쌍 S와 L에 대해, L 안에서 S 자체와 S에서 한 글자를 지워 만든 서로 다른 문자열, 한 글자를 넣어 만든 서로 다른 문자열이 나타나는 횟수를 센다.

난이도: 보통10점 중 4점
유형: 문자열, 해시맵, 문자열 매칭, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Technology has greatly changed the field of biology in the last decade, since biological information can be digitized and analyzed by computer. One of the most basic analysis tasks is counting the number of occurrences (or near-occurrences) of a search string S inside of another string L that is at least as long as S.

For this problem, you are given pairs of strings S and L. Both strings contain only the uppercase characters A, G, C, and T. For each of the following types of search strings, count the number of times that type occurs as an exact substring of L:

Type 1: S, without any changes.
Type 2: All unique strings that can be made by deleting one character from S (for example, AGC can become AG, AC, or GC).
Type 3: All unique strings that can be made by inserting one character in S (for example, AG can become any of the following: AAG, GAG, CAG, TAG, AGG, ACG, ATG, AGA, AGC, or AGT).

If two or more different modifications of S result in the same string, count only the occurrences of that string once.

입력

The input file contains multiple test cases, each of which contains two strings: S followed by L. The length of S is at least 2 characters and at most the length of L. The length of L is at most 100 characters. The last test case is followed by a line containing a single zero.

출력

For each test case, print the case number (beginning with 1) followed by the number of occurrences of Type 1, then Type 2, then Type 3.

예제1

예제 1

입력

AGCT AGCTAGCT
AAA AAAAAAAAAA
AGC TTTTGT
0

예상 출력

Case 1: 2 4 2
Case 2: 8 9 7
Case 3: 0 0 0