P1117 [NOI2016] Excellent Split

If a string can be split into the form $\text{AABB}$, where $\text{A}$ and $\text{B}$ are any non-empty strings, then we call this split of the string excellent. For example, for the string $\texttt{aabaabaa}$, if we set $\text{A}=\texttt{aab}$ and $\text{B}=\texttt{a}$, we have found one way to split this string into $\text{AABB}$. A string may have no excellent split, or it may have more than one excellent split. For example, if we set $\text{A}=\texttt{a}$ and $\text{B}=\texttt{baa}$, the above string can also be expressed as $\text{AABB}$; however, the string $\texttt{abaabaa}$ has no excellent split. Now given a string $S$ of length $n$, we need to count, over all substrings of $S$ and all their possible splits, the total number of excellent splits. Here a substring refers to a contiguous segment of the string. Notes: 1. Identical substrings that appear at different positions are considered different substrings, and their excellent splits are all counted in the answer. 2. In a split, $\text{A}=\text{B}$ is allowed. For example, $\texttt{cccc}$ has the split $\text{A}=\text{B}=\texttt{c}$. 3. The string itself is also one of its substrings.

Each input file contains multiple test cases. The first line of the input file contains a single integer $T$, indicating the number of test cases. Then follow $T$ lines, each containing a string $S$ consisting only of lowercase English letters, as described above.

Output $T$ lines. Each line contains an integer, indicating the total number of excellent splits among all splits of all substrings of $S$.

Sample explanation. We use $S[i, j]$ to denote the substring of $S$ from the $i$-th character to the $j$-th character (1-based indexing). In the first dataset, there are three substrings with excellent splits: $S[1,4]=\texttt{aabb}$, whose excellent split is $\text{A}=\texttt{a}$, $\text{B}=\texttt{b}$; $S[3,6]=\texttt{bbbb}$, whose excellent split is $\text{A}=\texttt{b}$, $\text{B}=\texttt{b}$; $S[1,6]=\texttt{aabbbb}$, whose excellent split is $\text{A}=\texttt{a}$, $\text{B}=\texttt{bb}$. The remaining substrings have no excellent splits, so the answer for the first dataset is $3$. In the second dataset, there are in total four substrings that have excellent splits, divided into two types: for the substrings $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$, they share the same excellent split $\text{A}=\texttt{c}$, $\text{B}=\texttt{c}$, but since these substrings are at different positions, they are counted three times; for the substring $S[1,6]=\texttt{cccccc}$, it has two excellent splits: $\text{A}=\texttt{c}$, $\text{B}=\texttt{cc}$ and $\text{A}=\texttt{cc}$, $\text{B}=\texttt{c}$, which are different splits of the same substring and are both counted. Therefore, the answer for the second dataset is $3+2=5$. In the third dataset, $S[1,8]$ and $S[4,11]$ each have two excellent splits. Among them, $S[1,8]$ is the example in the problem statement, so the answer is $2+2=4$. In the fourth dataset, $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, and $S[1,8]$ each have one excellent split, while $S[3,14]$ has two excellent splits, so the answer is $5+2=7$. ### Constraints For all test points, it is guaranteed that $1 \leq T \leq 10$. The following limits apply to a single input within a dataset; that is, within the same test point, all of its $T$ datasets satisfy the constraints. Let $n$ be the length of string $S$. The detailed constraints for each test point are shown in the table below: ::cute-table{tuack} | Test point ID | $n \leq$ | Special property | | :-----------: | :-------: | :------------------------------: | | $1 \sim 2$ | $300$ | All characters in $S$ are the same | | $3 \sim 4$ | $2\,000$ | ^ | | $5 \sim 6$ | $10$ | None | | $7 \sim 8$ | $20$ | ^ | | $9 \sim 10$ | $30$ | ^ | | $11 \sim 12$ | $50$ | ^ | | $13 \sim 14$ | $100$ | ^ | | $15$ | $200$ | ^ | | $16$ | $300$ | ^ | | $17$ | $500$ | ^ | | $18$ | $1\,000$ | ^ | | $19$ | $2\,000$ | ^ | | $20$ | $30\,000$ | ^ | Translated by ChatGPT 5