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 1-indexed.
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 ith symbol of the string S. Let's calculate the smallest index pi ≥ i such that the substring Si...Spi contains at least one of the strings generated by wildcard string T. In case any such index pi doesn't exist, then pi = -1.
Your goal is to calculate all the values p1, p2, ... , p|S|.
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.
For each test case, output a single line containing |S| space-separated integers, denoting p1, p2, ..., p|S|.
- 1 ≤ T ≤ 102
- Subtask 1 (33 points) : 1 ≤ sum of all |S|, sum of all |T| over a single test case ≤ 103, 1 ≤ |S|, |T| ≤ 102
- Subtask 2 (33 points) : 1 ≤ sum of all |S|, sum of all |T| over a single test case ≤ 105, 1 ≤ |S|, |T| ≤ 103
- Subtask 3 (34 points) : 1 ≤ sum of all |S|, sum of all |T| over a single test case ≤ 105, 1 ≤ |S|, |T| ≤ 105
- Total number of asterisks over all the test cases is at most 500.
Input: 2 *a* abacaba *a*b* abacaba Output: 1 3 3 5 5 7 7 2 6 6 6 6 -1 -1
Example case 1. Let us show that for every index i the value of pi is correct:
- p1 = 1. The corresponding substring a contains the string a. String a can be generated by replacing both asterisks with empty strings.
- p2 = 3. The corresponding substring ba contains the string a.
- p3 = 3. The corresponding substring a contains the string a.
- p4 = 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.
- p5 = 5. The corresponding substring a contains the string a.
- p6 = 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.
- p7 = 7. The corresponding substring a contains the string a.
Example case 2. Again, let's check for every i.
- p1 = 2. The corresponding substring ab contains ab. The string ab can be obtained if we replace all the asterisks with empty strings.
- p2 = 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.
- p3 = 6. The corresponding substring acab contains ab.
- p4 = 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.
- p5 = 6. The corresponding substring ab contains ab.
- p6 = p7 = -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.
|Tags||kmp, ltime28, medium-hard, pattern, string, xcwgf666|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.