Problems with backtracking algorithm in C++

I have to implement an algorithm that generates a modified version of a Thue Sequence, being that there can't be any adjacent sub-sequence can repeat itself using the letters N,P and O.

For example, NOPNO is a valid output but NOPNPNO is not because it repeats here NOPNPNO.

I tried to approach the problem using backtracking. My idea is to add a letter and check for repetitions until I get the right length that is required. You can check for more details of the problem here.

This is the code that I came up:

#include 
#include 

using namespace std;

bool found;

/* This function check, for every time a letter is added, if the sequence
 * is going to repeat itself. For each pair of substrings with length i
 * they are compared to check if they are equal.
 * ex:
 *  The sequence NONPNOPN will check if N = P, PN = NO, OPN = NPN, NOPN = NONP
 *
 * The function returns True if it should reject the sequence and False otherwise.
*/
bool reject(string str){
    int i = 1, len = str.size();
    while(i > n && n){
        found = false;
        cin.ignore();
        Thue(n,"");
    }
    return 0;
}

It is working fine but my problem is, it's too slow. I think my problem is the function to check for repetitions but I don't know how I can make it faster. How can I speed this up?

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 &str, int l1, int r1, int l2) {
  for (int i = l1, j = l2; i < r1; ++i, ++j) {
    if (str[i] != str[j])
      return false;
  }
  return true;
}

bool reject(const string &str) {
  int i = 1, len = str.size();
  while (i <= 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.

StackExchange Code Review Q#154612, answer score: 2