Problems with backtracking algorithm in C++
Observation 1

If you find a 5000-length NOP-sequence, an L-length prefix of it would be a valid nop-sequence. Hence computing a full-length nop-sequence once in the beginning and just outputting prefixes (or suffixes) of it will make things quicker.

Observation 2

Generating substrings and checking them will make code slow. Writing your own substring equality check will speed this up. In addition, pass the string by const reference because it is not going to be modified.

bool checkequal(const string &amp;str, int l1, int r1, int l2) {
  for (int i = l1, j = l2; i &lt; r1; ++i, ++j) {
    if (str[i] != str[j])
      return false;
  }
  return true;
}

bool reject(const string &amp;str) {
  int i = 1, len = str.size();
  while (i &lt;= len / 2) {
    if (checkequal(str, len - i, len, len - 2 * i))
      return true;
    i++;
  }
  return false;
}


These two improvements should make your code fast enough to be accepted in contest.