Pattern matching

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
You are given a string S, made of lowercase Latin letters.
You are also given a wildcard string T, containing lowercase latin letters and asterisks (symbol *).
Both the strings are 1indexed.
Wildcard string T is said to generate a string P if and only if P can be obtained from T by replacing all the asterisks with arbitrary (possibly empty) lowercase Latin letter strings.
Consider the i^{th} symbol of the string S. Let's calculate the smallest index p_{i} ≥ i such that the substring S_{i}...S_{pi} contains at least one of the strings generated by wildcard string T. In case any such index p_{i} doesn't exist, then p_{i} = 1.
Your goal is to calculate all the values p_{1}, p_{2}, ... , p_{S}.
Input
The first line of input contains an integer Tn denoting the number of test cases. The description of Tn test cases follows.
The first line of each test case contains a wildcard string T.
The second line of the test case contains a lowercase Latin string S.
Output
For each test case, output a single line containing S spaceseparated integers, denoting p_{1}, p_{2}, ..., p_{S}.
Constraints
 1 ≤ T ≤ 10^{2}
 Subtask 1 (33 points) : 1 ≤ sum of all S, sum of all T over a single test case ≤ 10^{3}, 1 ≤ S, T ≤ 10^{2}
 Subtask 2 (33 points) : 1 ≤ sum of all S, sum of all T over a single test case ≤ 10^{5}, 1 ≤ S, T ≤ 10^{3}
 Subtask 3 (34 points) : 1 ≤ sum of all S, sum of all T over a single test case ≤ 10^{5}, 1 ≤ S, T ≤ 10^{5}
 Total number of asterisks over all the test cases is at most 500.
Example
Input: 2 *a* abacaba *a*b* abacaba Output: 1 3 3 5 5 7 7 2 6 6 6 6 1 1
Explanation
Example case 1. Let us show that for every index i the value of p_{i} is correct:
 p_{1} = 1. The corresponding substring a contains the string a. String a can be generated by replacing both asterisks with empty strings.
 p_{2} = 3. The corresponding substring ba contains the string a.
 p_{3} = 3. The corresponding substring a contains the string a.
 p_{4} = 5. The corresponding substring ca contains the string ca. The string ca can be obtained if we replace the first asterisk with c and the second one with an empty string.
 p_{5} = 5. The corresponding substring a contains the string a.
 p_{6} = 7. The corresponding substring ba contains the string ba. The string ba can be obtained if we replace the first asterisk with b and the second one with an empty string.
 p_{7} = 7. The corresponding substring a contains the string a.
Example case 2. Again, let's check for every i.
 p_{1} = 2. The corresponding substring ab contains ab. The string ab can be obtained if we replace all the asterisks with empty strings.
 p_{2} = 6. The corresponding substring bacab contains acab. The string acab can be obtained if we replace the first asterisk with an empty string, the second one with the string ca and the third one with an empty string.
 p_{3} = 6. The corresponding substring acab contains ab.
 p_{4} = 6. The corresponding substring cab contains cab. The string cab can be obtained if you replace the first asterisk with c, and the rest with empty strings.
 p_{5} = 6. The corresponding substring ab contains ab.
 p_{6} = p_{7} = 1. Neither ba nor a doesn't contain any substring, generated by *a*b*.
You may have noted that in the explanation for the second test case, ab is also a correct substring generated by T for some positions, but some other string is listed. This is done on purpose, in order to show how the string T can generate various strings.
Author:  xcwgf666 
Tester:  logic_iu 
Editorial  http://discuss.codechef.com/problems/PATTMATC 
Tags  kmp, ltime28, mediumhard, pattern, string, xcwgf666 
Date Added:  24082015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions