[Solved] COMP 6651: Programming Assignment 1

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.