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?