SRM 701, D2, 250-Pointer (SquareFreeString)

James S. Plank

Fri Nov 4 13:59:03 EDT 2016
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:
  1. 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"

  2. 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"