Assignment 1 A repeat-once string


Rate this product

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
Sample Output
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.

Open chat
Need help?
Can we help you?