COMP 6651: Algorithm Design Techniques
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 (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
3
aba
xxx
ababab
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.
