P7114 [NOIP2020] String Matching

After learning about string matching, Little C is now working on a problem. For a string $S$, the task asks him to find the number of all split plans of $S$ that have one of the following forms: $S = ABC$, $S = ABABC$, $S = ABAB \ldots ABC$, where $A$, $B$, and $C$ are all non-empty strings, and the number of characters that appear an odd number of times in $A$ is not greater than the number of characters that appear an odd number of times in $C$. More specifically, we define $AB$ as the concatenation of two strings $A$ and $B$. For example, if $A = \texttt{aab}$ and $B = \texttt{ab}$, then $AB = \texttt{aabab}$. We also define recursively $A^1 = A$ and $A^n = A^{n - 1} A$ ($n \ge 2$ and $n$ is a positive integer). For example, if $A = \texttt{abb}$, then $A^3 = \texttt{abbabbabb}$. Then Little C's exercise is to find the number of plans such that $S = {(AB)}^i C$, where $F(A) \le F(C)$. Here, $F(S)$ denotes the number of characters that appear an odd number of times in the string $S$. Two plans are different if and only if at least one of the split strings $A$, $B$, and $C$ is different. Little C cannot solve this problem, so he asks you for help. Please help him.

This problem contains multiple test cases. The first line of the input file contains a positive integer $T$, indicating the number of test cases. Each test case contains one line with a string $S$, as described above. $S$ consists only of lowercase English letters.

For each test case, output one integer per line, representing the answer.

**【Sample #1 Explanation】** For the first test case, all valid plans are: 1. $A = \texttt{n}$, $B = \texttt{nr}$, $C = \texttt{nnr}$. 2. $A = \texttt{n}$, $B = \texttt{nrn}$, $C = \texttt{nr}$. 3. $A = \texttt{n}$, $B = \texttt{nrnn}$, $C = \texttt{r}$. 4. $A = \texttt{nn}$, $B = \texttt{r}$, $C = \texttt{nnr}$. 5. $A = \texttt{nn}$, $B = \texttt{rn}$, $C = \texttt{nr}$. 6. $A = \texttt{nn}$, $B = \texttt{rnn}$, $C = \texttt{r}$. 7. $A = \texttt{nnr}$, $B = \texttt{n}$, $C = \texttt{nr}$. 8. $A = \texttt{nnr}$, $B = \texttt{nn}$, $C = \texttt{r}$. **【Constraints】** | Test Point ID | $\lvert S \rvert \le$ | Special Property | |:-:|:-:|:-:| | $1 \sim 4$ | $10$ | None | | $5 \sim 8$ | $100$ | None | | $9 \sim 12$ | $1000$ | None | | $13 \sim 14$ | $2^{15}$ | $S$ contains only one kind of character | | $15 \sim 17$ | $2^{16}$ | $S$ contains only two kinds of characters | | $18 \sim 21$ | $2^{17}$ | None | | $22 \sim 25$ | $2^{20}$ | None | For all test points, it is guaranteed that $1 \le T \le 5$ and $1 \le |S| \le 2^{20}$. Translated by ChatGPT 5