### PROBLEM LINK:

**Author:** Sergey Kulik

**Tester:** Yanpei Liu

**Editorialist:** Pawel Kacprzak

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

Strings, Pattern matching, KMP

### PROBLEM:

The problem is stated really simple. You are given a string S of N lowercase Latin letters. In addition, you are given a **wildcard** string T, of length M, consisting of lowercase Latin characters and asterisk symbols ‘*’.

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:

Split T on asterisks to get a list L of patterns. Find occurences of all patterns from L in S. For each suffix S[i..N] of S, find in S[i..N], the leftmost chain of non overlapping occurrences of all consecutive patterns from L.

### EXPLANATION:

The first observations, which we can make, is that, we can replace any run of more than one asterisk with a single one.

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, non-overlapping occurrences of all consecutive patterns from L, which is equivalent to the leftmost occurrence of a string generated by wildcard string T.

## Time Complexity

Notice that, the time complexity of this approach depends on the method used to find occurrences of patterns from L in S.

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.

Tester’s solution can be found here.