Song of the Sirens
Contest: Good Bye 2020
Difficulty rating: 2600
Tags: combinatorics, divide and conquer, hashing, math, string suffix structures, strings

In the times of Jason and the Argonauts, it was well known that sirens use the sound of their songs to lure sailors into their demise. Yet only a few knew that every time sirens call a sailor by his name, his will weakens, making him more vulnerable.

For the purpose of this problem, both siren songs and names of the sailors will be represented as strings of lowercase English letters. The more times the sailor's name occurs as a contiguous substring of the song, the greater danger he is in.

Jason found out that sirens can sing one of the $$$n+1$$$ songs, which have the following structure: let $$$s_i$$$ ($$$0 \leq i \leq n$$$) be the $$$i$$$-th song and $$$t$$$ be a string of length $$$n$$$, then for every $$$i < n$$$: $$$s_{i+1} = s_i t_i s_i$$$. In other words $$$i+1$$$-st song is the concatenation of $$$i$$$-th song, $$$i$$$-th letter ($$$0$$$-indexed) of $$$t$$$ and the $$$i$$$-th song.

Fortunately, he also knows $$$s_0$$$ and $$$t$$$. Jason wonders how many times a sailor's name is mentioned in a particular song. Answer $$$q$$$ queries: given the sailor's name ($$$w$$$) and the index of a song ($$$i$$$) output the number of occurrences of $$$w$$$ in $$$s_i$$$ as a substring. As this number can be quite large, output its remainder modulo $$$10^9+7$$$.

Input format:
In the first line of input there are two integers $$$n$$$, $$$q$$$ ( $$$ 1 \leq n, q \leq 10^5$$$) meaning that there are $$$n+1$$$ songs and $$$q$$$ queries. In the next two lines strings $$$s_0$$$ and $$$t$$$ follow ($$$1 \leq |s_0| \leq 100, |t| = n$$$).

Next $$$q$$$ lines describe the queries; each one contains an integer $$$k$$$ ($$$ 0 \leq k \leq n$$$), the index of the song sung by the sirens, and a non-empty string $$$w$$$, which is the name of a sailor. All strings in this problem consist only of lowercase English letters, and the sum of lengths of sailors' names does not exceed $$$10^6$$$.

Output format:
Output $$$q$$$ lines, $$$i$$$-th of them should contain the remainder modulo $$$10^9+7$$$ of the number of occurrences of $$$w$$$ in $$$s_k$$$.

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

Note:
In the first example songs of the sirens are as follows:

- Song $$$0$$$: aa
- Song $$$1$$$: aabaa
- Song $$$2$$$: aabaacaabaa
- Song $$$3$$$: aabaacaabaadaabaacaabaa

Example input:
3 3
aa
bcd
2 aba
3 ca
3 aa

Example output:
2
2
8

Example input:
4 5
aba
bbac
1 a
3 baca
3 ab
2 bab
4 aba

Example output:
4
0
14
6
28

Editorial:
We define $$$f(n, w)$$$ as the number of occurrences of $$$w$$$ in $$$s_n$$$. Moreover, we define $$$g(n, w), n > 0$$$ as the number of occurrences of $$$w$$$ in $$$s_n$$$ which contain character $$$t_{n - 1}$$$. With these definitions, we write the formula for $$$f(n, w)$$$ with $$$n > 0$$$: $$$$$$ f(n, w) = 2 \cdot f(n - 1, w) + g(n, w) = f(0, w) \cdot 2^n + \sum_{k = 1}^n g(k, w) \cdot 2^{n - k} $$$$$$
Let $$$s_k$$$ be the shortest song, such that $$$|w| \leq |s_k|$$$. Notice that $$$|s_k| \leq 2 \cdot |w| + |s_0|$$$. We can further reformulate the formula for $$$f(n, w)$$$: $$$$$$ f(n, w) = f(k, w) \cdot 2^{n - k} + \sum_{i = k + 1}^n g(i, w) \cdot 2^{n - i} $$$$$$
The length of $$$s_k$$$ is more or less the same as the length of $$$w$$$, so we can brute-force all occurrences of $$$w$$$ in $$$s_k$$$ with, for example, the KMP algorithm.
The key observation to calculate the latter part of the formula is that $$$g(i, w)$$$ = $$$g(j, w)$$$ if $$$t_{i - 1} = t_{j - 1}$$$, and $$$k < i, j$$$. To prove that we note that $$$s_i, s_j$$$ can be represented as: $$$$$$ s_i = a_i \, s_k \, t_{i - 1} \, s_k \, b_i \\ s_j = a_j \, s_k \, t_{j - 1} \, s_k \, b_j \\ $$$$$$
As $$$|w| \leq |s_k|$$$, and we are interested only in occurrences containing the middle character, we can see that for equal $$$t_{i - 1}$$$, $$$t_{j - 1}$$$, values of $$$g$$$ are the same.
We calculate the value of the $$$g$$$ function for each letter of the alphabet (we can use KMP for this). Using prefix sums we can calculate $$$\sum_{i = k + 1}^n g(i, w) \cdot 2^{n - i}$$$ in $$$\mathcal{O}(|\Sigma|)$$$, where $$$|\Sigma|$$$ denotes the length of the alphabet.
The whole algorithm works in $$$\mathcal{O}(n + q \cdot (|\Sigma| + |s_0|) + S)$$$, where $$$S$$$ denotes the total length of all queries. It can be improved to $$$\mathcal{O}(n + q + S)$$$, but it was not needed to get accepted.