// This code correspond to the exhaustive search for the lower bounds on d(i) in Theorem 9 of
// "How far away must forced letters be so that squares are still avoidable?"
// It should be compiled with c++11 or higher and optimization O3 wich gives:
//      g++ lower_bounds_on_d.cpp -O3 -o <executable_name>

#include <iostream>
#include <string>
using namespace std;

bool hasSquareLast(const string& word){//checks whether one of the suffix of the word is a square
  int s = word.size();
	for(int i = 1; i*2<=s; i++){
		bool isrep = true;
		for(int j=0; j<i; j++){
			if(word[s-1-j]!= word[s-1-j-i]){
				isrep = false;
				break;
			}
		}
		if(isrep) return true;
	}
	return false;
}

int maxl=0, tot =0;
void findWords(int sA, int d, string &word){//The exhaustive search is done by a recursive algorithm
  //if the last letter is at a "forced" position, we check that it has the "forced" value
  if(!hasSquareLast(word) && !(word.size()%d == 1 && word.back() != 'a'+((word.size()/d)%sA))){
    tot++;
    maxl = max(maxl, int(word.size()));
    word += "a";
    for(word.back() = 'a'; word.back() < 'a'+sA; word.back()++) findWords(sA, d, word);
    word.pop_back();
  }
}

int main (int argc, char *argv[]){
  cout<<"Enter 3 to check that d({0,1,2})>6 or 4 to check that d({0,1,2,3})>2"<<endl;
  int input;
  cin>> input;
  string w("");
  if(input == 3) findWords(3, 6, w);
  else if(input== 4) findWords(4, 2, w);
  else cout<<"Enter 3 to check that d({0,1,2})>6 or 4 to check that d({0,1,2,3})>2"<<endl;
  cout <<"The longest word has length "<< maxl<<"   and the number of different words is "<<tot<<"."<<endl;
	return 0;
}