COMP 6651: Programming Assignment 1 Solved

25.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

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 (aâˆ’z).

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.

• repeat-once-strings.zip