Prefix Function Queries
Contest: Educational Codeforces Round 134 (Rated for Div. 2)
Difficulty rating: 2200
Tags: dfs and similar, dp, hashing, string suffix structures, strings, trees

You are given a string $$$s$$$, consisting of lowercase Latin letters.

You are asked $$$q$$$ queries about it: given another string $$$t$$$, consisting of lowercase Latin letters, perform the following steps:

1. concatenate $$$s$$$ and $$$t$$$;
2. calculate the prefix function of the resulting string $$$s+t$$$;
3. print the values of the prefix function on positions $$$|s|+1, |s|+2, \dots, |s|+|t|$$$ ($$$|s|$$$ and $$$|t|$$$ denote the lengths of strings $$$s$$$ and $$$t$$$, respectively);
4. revert the string back to $$$s$$$.

The prefix function of a string $$$a$$$ is a sequence $$$p_1, p_2, \dots, p_{|a|}$$$, where $$$p_i$$$ is the maximum value of $$$k$$$ such that $$$k < i$$$ and $$$a[1..k]=a[i-k+1..i]$$$ ($$$a[l..r]$$$ denotes a contiguous substring of a string $$$a$$$ from a position $$$l$$$ to a position $$$r$$$, inclusive). In other words, it's the longest proper prefix of the string $$$a[1..i]$$$ that is equal to its suffix of the same length.

Input format:
The first line contains a non-empty string $$$s$$$ ($$$1 \le |s| \le 10^6$$$), consisting of lowercase Latin letters.

The second line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains a query: a non-empty string $$$t$$$ ($$$1 \le |t| \le 10$$$), consisting of lowercase Latin letters.

Output format:
For each query, print the values of the prefix function of a string $$$s+t$$$ on positions $$$|s|+1, |s|+2, \dots, |s|+|t|$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
aba
6
caba
aba
bababa
aaaa
b
forces

Example output:
0 1 2 3 
1 2 3 
2 3 4 5 6 7 
1 1 1 1 
2 
0 0 0 0 0 0

Example input:
aacba
4
aaca
cbbb
aab
ccaca

Example output:
2 2 3 1 
0 0 0 0 
2 2 0 
0 0 1 0 1

Editorial:
What's the issue with calculating the prefix function on the string $$$s$$$ and then appending the string $$$t$$$ with an extra $$$|t|$$$ recalculations? Calculating prefix function is linear anyway. Well, it's linear, but it's also amortized. So while it will make $$$O(n)$$$ operations for a string in total, it can take up to $$$O(n)$$$ on every particular letter. These particular letters can appear in string $$$t$$$, making the algorithm work in $$$O(q \cdot (|s| + |t|))$$$.
Let's analyze the classic way to calculate the prefix function. To append a character to the string and calculate the new value of the prefix function, you have to do the following:
1. take the longest proper prefix of a string before appending the letter, which is also a suffix;
2. if the letter right after it is the same as the new one, then the new value is length of it plus one;
3. if it's empty, then the new value is $$$0$$$;
4. otherwise, take its longest proper prefix and return to step $$$2$$$.
Basically, from having the value of the prefix function of the string and the new letter, you can determine the new value of the prefix function.
If $$$|t|$$$ was always equal to $$$1$$$, then you would only want to try all options for the next letter after a string.
That should remind you of a structure known as prefix function automaton. Its states are the values of the prefix function, and the transitions are appending a letter to a string with a certain value of the prefix function.
So you can append a letter in $$$O(1)$$$ if you have an automaton built on the string $$$s$$$. However, you can't just append more letters after one — you don't have the automaton built this far.
You can follow two paths.
The first one is to jump with a regular way of calculating the prefix function until you reach the state of the automaton which exists.
The second one is to continue building the automaton onto the string $$$t$$$, calculating the prefix function along the way. Appending a layer to the automaton takes $$$O(\mathit{AL})$$$ non-amortized. After you calculated everything you needed, pop the states back to the original.
Overall complexity: $$$O(|s| \cdot \mathit{AL} + q \cdot |t|)$$$ or $$$O(|s| \cdot \mathit{AL} + q \cdot |t| \cdot \mathit{AL})$$$.