1 Problem
A string is called a repeat-once string if we can obtain it by concatenating two copies of the same string. For example, xxyxxy and xx are repeat-once strings, while xxx and xyyx are not. Given a string, calculate the number of non-empty subsequences of the string such that they are repeat-once strings. For example, given the string xxx it has three subsequences that are repeat-once strings, each of them is xx (the first and second x from xxx, the second and third x, and the first and third x).
2 Input
The first line of the input is an integer T, which is the number of test cases. The next T lines contain test cases, each of which contains a string. You can assume that 1 T 200 and that each string in the test case is of length at most 200, and consists only of lower-case letters (az).
3 Output
For each test case, list the number of repeat-once subsequences on a separate line. The output should therefore have T different lines.
4 Example
Sample Input
Sample Output
1
3
12
Explanation
For the first test case, there is only one repeat-once subsequence, namely aa. For the second, there are 3 identical repeat-once subsequences xx. For the last test case, there are the following repeat-once subsequences: aa (3), bb (3), ab (5), and ba(1)
5 Requirements
For the constraints given above, your program should run in 3 seconds. You must submit source code for a program written in C/C++/Java on the Electronic Assignment System. Some test cases will be provided on the course website. You can verify if your program works on the test cases before submitting.
6 Programmer-on-duty
There will be a programmer-on-duty, Tejas Puranik, available to help you with the assignment on Wednesdays 6pm to 9pm in H841.
Reviews
There are no reviews yet.