Problems with backtracking algorithm in C++

Question

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 <string>
#include <iostream>

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 <= len/2){
        if(str.substr(len-2*i,i) == str.substr(len-i,i)) return true;
        i++;
    }
    return false;
}

/* This function uses backtracking to generate the answers. It recursively adds
 * a letter to the string and checks if it is a probable candidate, printing the answer if
 * it's the right answer and returning otherwise
*/
void Thue(int n, string str){
    if(found) return;
    if(reject(str)) return;

    if(str.size() == n){
        cout << str << endl;
        found = true;
        return;
    }

    Thue(n,str+"N");
    Thue(n,str+"O");
    Thue(n,str+"P");
}

int main(){
    int n;
    while(cin >> 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?

Answer 1

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.

Answer 2

Thue sequence generation

If you search online, you will find that there is a known way to generate an infinite length Thue sequence. For example, this webpage shows us the recursive formula:

A -> ABC
B -> AC
C -> B

So all you have to do is start with "A", and then on each generation pass, you replace each symbol with the replacement sequence.

"A"   -> "ABC"
"ABC" -> "ABCACB" (ABC + AC + B)
etc.

This algorithm should take \$O(n)\$ time to find a sequence of length \$n\$ because each pass roughly doubles the sequence size.

Sample program

Here is a sample program which uses the above algorithm to solve your problem:

#include <string>
#include <iostream>

#define MAX        5000

// A square free sequence is a sequence where the pattern XX does not
// appear in the sequence for all subsequences X.  For example, NOPOPN has
// the sequence OP-OP occur which makes it not a square free sequence.

// Objective, given a 3 character alphabet {N, O, P}, generate a square free
// sequence of length K.

// Strategy: The Thue sequence is an infinite square free sequence generated
// from the following rule:
//
// A -> ABC
// B -> AC
// C -> B
//
// Start with the sequence "A".  On each generation, replace each symbol
// in the sequence with the replacement sequence.

void generate(std::string &sequence, int *pLen)
{
    int len    = *pLen;
    int i      = 0;
    int j      = 0;
    std::string old(sequence);

    for (i=0;i<len;i++) {
        switch (old[i]) {
            case 'N':
                sequence[j++] = 'N';
                sequence[j++] = 'O';
                sequence[j++] = 'P';
                break;
            case 'O':
                sequence[j++] = 'N';
                sequence[j++] = 'P';
                break;
            case 'P':
                sequence[j++] = 'O';
                break;
        }
    }
    *pLen = j;
}

int main(void)
{
    int n;
    std::string sequence;
    int sequenceLen = 1;

    sequence.resize(MAX * 3, 'N');
    while (sequenceLen < MAX) {
        generate(sequence, &sequenceLen);
    }
    while (std::cin >> n && n) {
        std::string substr(sequence, 0, n);
        std::cout << substr << "\n";
    }
}