| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 19 | 10 | 9 | 90.000% |
If a string can be written in the form of AABB where A and B are arbitrary non-empty strings, then we say this is a good partition. For example, it is possible to write the string aabaabaa in the form of AABB by letting A = aab and B = a.
Some strings do not admit a good partition, while some strings admit multiple good partitions. For example, for the above string aabaabaa, it is also possible to write it in the form of AABB by letting A = a and B = baa. The string abaabaa does not admit good partitions.
Given a string $S$ of length $n,ドル compute the sum, over all its substrings, of the number of good partitions of those substrings. Here, substring refers to a contiguous part of the string.
Please pay attention to the following details:
A = B in a good partition. For example, the string cccc admits good partition A = B = c.Each input file has several test cases.
The first line of the input file contains one integer $T$ denoting the number of test cases in the file.
In the following $T$ lines, each line contains a string $S$ consisting of lower-case English letters.
Output $T$ lines: each line consists of an integer denoting the total number of good partitions among all possible partitions of substrings of $S$.
For all test cases, 1ドル \leq T \leq 10, n \leq 30,000円$.
4 aabbbb cccccc aabaabaabaa bbaabaababaaba
3 5 4 7
Let $S[i,j]$ denote the substring of $S$ consisting of the $i$-th character to the $j$-th character of $S,ドル with index starting from 1.
In the first test case, there are three substrings admitting good partitions: $S[1,4] =$ aabb with A = a, B = b, $S[3,6] =$ bbbb with A = b, B = b, and $S[1,6] =$ aabbbb with $A = a, B = bb$. Other substrings of $S$ does not admit good partitions, so the answer shall be 3.
In the second test case, $S[1,4] = S[2,5] = S[3,6] =$ cccc admit good partition A = c, B = c, so the total contribution to the final answer is 3. For string $S[1,6] =$ cccccc, it admits two good partitions (A = c, B = cc or A = cc, B = c). The different good partitions corresponding to the same substring should all count towards the final answer, so the final answer to the second test case is 3ドル + 2 = 5$.
In the third test case, $S[1,8]$ and $S[4,11]$ admits two good partitions respectively. $S[1,8]$ is the example described in the problem description. The answer should be 2ドル + 2 = 4$.
In the fourth test case, each of $S[1,4], S[6,11], S[7,12], S[2,11], S[1,8]$ admits one good partition, and $S[3,14]$ admits two good partitions, so the answer should be 5ドル + 2 = 7$.
See ex_excellent2.in and ex_excellent2.ans .
See ex_excellent3.in and ex_excellent3.ans .