Codeforces Round 857 (Div. 1) |
---|
Finished |
To do this, he took the string $$$t$$$ and a set of $$$n$$$ strings $$$s_1$$$, $$$s_2$$$, $$$s_3$$$, ..., $$$s_n$$$. Philip has $$$m$$$ queries, in the $$$i$$$th of them, Philip wants to take a substring of the string $$$t$$$ from $$$l_i$$$th to $$$r_i$$$th character, and count the number of its substrings that match some string from the set. More formally, Philip wants to count the number of pairs of positions $$$a$$$, $$$b$$$, such that $$$l_i \le a \le b \le r_i$$$, and the substring of the string $$$t$$$ from $$$a$$$th to $$$b$$$th character coincides with some string $$$s_j$$$ from the set.
A substring of the string $$$t$$$ from $$$a$$$th to $$$b$$$th character is a string obtained from $$$t$$$ by removing the $$$a - 1$$$ character from the beginning and $$$|t| - b$$$ characters from the end, where $$$|t|$$$ denotes the length of the string $$$t$$$.
Philip has already solved this problem, but can you?
The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 500\,000$$$) — the number of rows in the set and the number of queries.
The second line contains a single string $$$t$$$ consisting of lowercase letters of the English alphabet ($$$1 \le |t| \le 5 \cdot 10^6$$$).
The following $$$n$$$ lines describe the strings from the set. In the $$$i$$$th of them, a single string $$$s_i$$$ is given, consisting of lowercase letters of the English alphabet. Denote by $$$S$$$ the total length of all strings from the set. It is guaranteed that $$$S \le 10^6$$$, as well as that all strings of $$$s_i$$$ are different.
In the following lines, queries are entered. The $$$i$$$th of them contains two positive integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le |t|$$$) — the left and right border of the substring $$$t$$$ from the $$$i$$$-th query.
In a single line, print $$$m$$$ integers, $$$i$$$th of them should be equal to the answers to the $$$i$$$th query.
3 5 abacaba aba a ac 1 7 1 3 2 7 2 5 4 5
7 3 5 3 1
4 4 abcdca ab ca bcd openolympiad 1 5 2 2 2 6 1 6
2 0 2 3
In the first example, the first query requires the entire string to count the number of substrings that are included in the set. The substrings $$$[1, 3]$$$ and $$$[4, 6]$$$ coincide with the string "aba". The substrings match with the string "a" $$$[1, 1]$$$, $$$[3, 3]$$$, $$$[5, 5]$$$, $$$[7, 7]$$$. The substring $$$[3, 4]$$$ matches the string "ac". In total, it turns out that 7 substrings of the string "abacaba" match the strings from the set.
In the second query, a substring from position 1 to position 3 is taken from the source string, this is the string "aba". The string "aba" enters it 1 time, the string "a" enters it 2 times and the string "ac" does not enter it once as a substring. In the third query, a substring from the 2nd to the 7th position is taken from the source string, this is the string "bacaba". The string "aba" is included in it 1 time, the string "a" is included 3 times and the string "ac" is included 1 time as a substring.
Name |
---|