TopCoder SRM 701 SquareFreeString

TopCoder Statistics - Problem Statement

This problem is Easy. Note that write clean and easy-reading code, do not use much tricky. Because it may cause some bugs that can not be found easily. For each substring, compare the first half of the substring to the second half of the substring. Loop the substrings by length.

#include <bits/stdc++.h>

using namespace std;

class SquareFreeString {
public:
  string isSquareFree(string s) {
    string s1 = "square-free", s2 = "not square-free";

    for (int len = 2; len <= int(s.size()); len += 2) {
      for (int j = 0; j <= int(s.size())-len; ++j) {
    if (check(s.substr(j, len))) {
      return s2;
    }
      }
    }
    return s1;
  }
  bool check(string s) {
    int len = s.size() / 2;
    for (int i = 0; i < len; ++i) {
      if (s[i] != s[i+len]) return false;
    }
    return true;
  }
};

int main(void) {
  SquareFreeString s;
  vector<string> a{ "bobo", "apple", "pen", "aydyamrbnauhftmphyrooyq",
      "qwertyuiopasdfghjklzxcvbnm" };
                
  for (auto ss : a) {
    cout << s.isSquareFree(ss) << endl;
  }

  return 0;
}