SRM 701, D2, 250-Pointer (SquareFreeString)

James S. Plank

Fri Nov 4 13:59:03 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: October, 2016
Competitors who opened the problem: 374
Competitors who submitted a solution: 346
Number of correct solutions: 257
Accuracy (percentage correct vs those who opened): 68.7%
Average Correct Time: 17 minutes, 12 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

A "square" string is an even-length string where the first half of the string equals the second half. Examples are "aa", "abab" and "bolbol".
You are given a string. If this string has no substrings that are square, then you must return "square-free". Otherwise, you return "not square-free".
The string's size will be between 1 and 50 characters.
The characters will all be lower-case.

Examples

#  String                       Return Value
-  ------                       -------------
0  "bobo"                       "not square-free": The whole string is a square string.
1  "apple"                      "not square-free": Substring "pp" is a square string.
2  "pen"                        "square-free": No square substrings.
3  "aydyamrbnauhftmphyrooyq"    "not square-free"
4  "qwertyuiopasdfghjklzxcvbnm" "square-free"

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Hints

This is an enumeration and string problem. Try this on your own with no hints, and if you get stuck or frustrated, come back here and scroll down.

There are many ways to approach the enumeration. Here are two of them:

Enumerate all starting positions for the substring, and then all lengths for the first half of the substring. For example, suppose the string is "abcdefg". Then your enumeration will go as follows:

Starting position	Length of first half	First half	Second half
0	1	"a"	"b"
0	2	"ab"	"cd"
0	3	"abc"	"def"
0	4	"abcd"	Not big enough: Next starting position
1	1	"b"	"c"
1	2	"bc"	"de"
1	3	"bcd"	"efg"
1	4	"bcde"	Not big enough: Next starting position
2	1	"c"	"d"
2	2	"cd"	"ef"
2	3	"cde"	Not big enough: Next starting position
3	1	"d"	"e"
3	2	"de"	"fg"
3	3	"def"	Not big enough: Next starting position
4	1	"e"	"f"
4	2	"ef"	Not big enough: Next starting position
5	1	"f"	"g"
5	2	"fg"	Not big enough: Next starting position
6	1	"g"	Not big enough: Next starting position
7 = End of string - return "square-free"

Enumerate all even-length strings. For each of these, check to see if the first half equals the second half. Let's use an example string of "abcdede":

Starting position	Size of string	String	First half equals second half?
0	2	"ab"	No.
0	4	"abcd"	No.
0	6	"abcded"	No.
1	2	"bc"	No.
1	4	"bcde"	No.
1	6	"bcdede"	No.
2	2	"cd"	No.
2	4	"cded"	No.
3	2	"de"	No.
3	4	"dede"	Yes - return "not square-free"

Both of these approaches are O(n²) where n is the size of the string. You might be thinking, "This isn't your standard all-pairs enumeration -- it is smaller. Shouldn't it be less than O(n²)?." Think about the second one -- it's the summation of (n-i)/2 for all i. So, it's roughly half of the summation of i for all i. A half of O(n²) is still O(n²).