P8006 String Rearrangement in Phantom

Given a string $S$, each query provides two substrings $S[l_1, r_1]$ and $S[l_2, r_2]$. You need to count how many ways to split $S[l_1, r_1]$ such that $S[l_1, r_1] = A + B + C$ and $C + B^R + A = S[l_2, r_2]$. Here, $B^R$ means the reverse of string $B$, $+$ means string concatenation, and $S[l, r]$ means taking the $l$-th to the $r$-th characters of $S$. Strings $A$, $B$, and $C$ can be empty.

The first line contains two positive integers $n$ and $m$, representing the length of $S$ and the number of queries. The second line contains a string of length $n$ consisting of lowercase letters, representing $S$. The next $m$ lines each contain four positive integers $l_1, r_1, l_2, r_2$, representing the query intervals. It is guaranteed that $r_1 - l_1 = r_2 - l_2$.

Output $m$ lines, each containing one positive integer, representing the answer.

**This problem uses bundled testdata.** | Subtask ID | Score | Special Constraints | | :----------: | :----------: | :----------: | | $0$ | $10$ | $1\le n,m\le 100$ | | $1$ | $10$ | $1\le n,m\le 500$ | | $2$ | $20$ | $1\le n,m\le 3000$ | | $3$ | $30$ | $1\le n,m\le 5\times 10^4$ | | $4$ | $30$ | $1\le n\le 2\times 10^5$，$1\le m\le 10^5$ | For all testdata, it is guaranteed that $1\le n\le 2\times 10^5$, $1\le m\le 10^5$, $1\le l_1\le r_1\le n$, $1\le l_2\le r_2\le n$, and $r_1 - l_1 = r_2 - l_2$. For Subtask $i$, the time limit is $i + 1$ seconds. Translated by ChatGPT 5