RootOfAString.cpp

/*
 * @author: basicxman
 * @description: http://dwite.ca/questions/cs4hs_root_of_a_string.html
 */

#include <iostream>
using namespace std;

bool TestRoot(string root, string s) {
  int n = s.length();
  int w = root.length();
  if (n % w != 0) return false;
  int rep = n / w;

  string substr = "";
  for (int i = 0; i < rep; i++) substr.append(root);
  return substr == s;
}

string GetStringRoot(string s) {
  int n = s.length();
  if (n <= 1) return s;

  string substr;
  for (int i = 1; i < n; i++) {
    substr = s.substr(0, i);
    if (TestRoot(substr, s)) break;
  }
  return substr;
}

int main(int argc, char **argv) {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  string s;
  while (cin >> s)
    cout << GetStringRoot(s) << endl;

  return 0;
}