Good string - MarisaOJ: Marisa Online Judge

Good string

Time limit: 1000 ms
Memory limit: 256 MB
A string is considered good if it can be written in the form AABB with A and B being non-empty strings. For example, the string ababaa is a good string because it can be formed by taking A=ab and B=a. A and B can be equal. Given a string S, count the number of consecutive substrings of S that are good strings. ### Input - The first line contains an integer T, the number of strings to process. - The next T lines each contain a string S corresponding to a test case. ### Output - For each string, print an integer, the answer. ### Example Input: 4aabaabaabaabaaaabaababaaba Output: 3547 ### Constraints In each test case: - 1≤T≤10,1≤n≤30000.
Test n≤ Special condition
1,2 300 All characters in S are similar
3,4 2000
5,6 10 None
7,8 20
9,10 30
11,12 50
13,14 100
15 200
16 300
17 500
18 1000
19 2000
20 30000