PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:MediumHard PREREQUISITES:Strings, Pattern matching, KMP PROBLEM:
We said that $T$ generates a string $P$, if and only if, $P$ can be obtained from $T$ by replacing all the asterisks with any, even empty, lowercase Latin letter strings. The task is, for each suffix $S[i..N]$ of $S$, compute the position of the first occurrence in this suffix, of a string $P$, which can be generated from $T$. QUICK EXPLANATION:
EXPLANATION:
After that, we can split $T$ on asterisks and get a list $L$ of $K$ patterns, where $K$ is not greater that the number of asterisks + 1. The general idea is to use a pattern matching algorithm to find all occurrences of each pattern from $L$ in $S$. Since we know that the number of asterisks is at most $500$, we can compute the array $A[i][j]$, where $A[i][j] = b$, if and only if, the first occurrence of the $j^{th}$ pattern from $L$ in $S[i..N]$ is at index $b$ in $S$. Based on the above idea, we can iterate over all suffixes of $S$, and for each of them, using the $A$ array, we can easily compute the leftmost, nonoverlapping occurrences of all consecutive patterns from $L$, which is equivalent to the leftmost occurrence of a string generated by wildcard string $T$. Time Complexity
Naive pattern matching can be sufficient to pass some subtasks, but if you want a full credit, and we hope you do, you have to use any linear pattern matching algorithm, like KMP for example. If you do that, the total time complexity of a single test case is $O(K \cdot N)$, because we use linear pattern matching to find occurrences of $K$ patterns in a string of length $N$, and next, for each of $N$ suffixes, we make at most $K$ jumps over $A$ array. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 27 Sep '15, 08:36

To previus: It is because the string "bacb" CONTAINS the string generated from "a*b" (which is "acb"). So 5 should be a correct answer at i=2. I had the same mistake as you with this problem during the contest and it took me about an hour before I can realize that :( answered 27 Sep '15, 22:18

In this case: 1 ab abacb I got this: 2 5 5 1 1 from tester and Author solution, but I think for i = 2, you can't get s[2, 5]=bacb from a * b, because there are not '' at the begining of T The answer should be 2 1 5 1 1 , anyone? answered 27 Sep '15, 14:30
