P6629 [ZJOI2020] String.

3 s, 512 MB.

Bob likes strings. Bob thinks that a string repeated twice is beautiful. For example, `aa`, `sese`, `abcabc`, `baabaa`, `abababab` are beautiful strings, while `ab`, `aadead`, `sesese`, `abba` are not. More specifically, if a string $S$ can be written as the concatenation of two identical strings, that is, there exists a string $P$ such that $S = PP$, then $S$ is beautiful. Bob has a string $T = T_1 T_2 \cdots T_n$ of length $n$. Now he wants to know: given a substring $Q = T[l \cdots r]$ of $T$, how many essentially different beautiful strings appear as substrings within this substring $Q$. If two strings are the same but occur at different positions, then they are not considered essentially different. Bob has $q$ different queries in total. You need to compute the answers quickly.

The first line contains two integers $n, q$. The second line contains a string $T$ consisting only of lowercase letters `a` and `b`. In the next $q$ lines, each line contains two integers $l, r$, representing one query.

Output $q$ lines, each with one integer representing the answer.

Sample explanation 1: In $T$, the essentially different beautiful strings are `aa`, `aaaa`, `abaaba`, `aabaab`, `baabaa`. Sample input/output 2 is provided in the attachment. Constraints: For the first $10\%$ of the testdata, $n \leq 100$. For the first $20\%$ of the testdata, $n \leq 500$. For the first $40\%$ of the testdata, $n \leq 5000$. For another $20\%$ of the testdata, it is guaranteed that the total number of beautiful substrings in $T$ does not exceed $10^6$, where substrings at different positions are considered different. For another $20\%$ of the testdata, $q = 1$. For $100\%$ of the testdata, $1 \leq n, q \leq 200000$, $1 \leq l \leq r \leq n$. $T$ contains only lowercase letters `a` and `b`. Translated by ChatGPT 5