Hide

Problem D
Genetic Search

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.

Input

The input contains up to $250$ test cases, each of which is a line containing strings $S$ and $L$, separated by a single space. The constraints are $2 \le |S| \le |L| \le 100$. Each string consists only of the characters A, G, C, and T. The last test case is followed by a line containing a single zero.

Output

For each test case, output the number of occurrences of Type 1, then Type 2, then Type 3.

Sample Input 1 Sample Output 1
AGCT AGCTAGCT
AAA AAAAAAAAAA
AGC TTTTGT
0
2 4 2
8 9 7
0 0 0

Please log in to submit a solution to this problem

Log in