#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <time.h>

using namespace std;

void printEspecial(string s, int n)
{
   string r;
 
   for(int i = n; i < pow(2,n); i++)
   {
      if((s[i] + 1) % 2)
         r += "1";
      else
         r += "0";
   }
   
   for(int i = 0; i < n; i++)
      r += "1";
      
   cout << "[APP]Sequencia de bruijn: " << r << endl;
}


int main() 
{
   // Atributos
   int n;
   string subString;
   string sequencia;

   // Pegando o valor de n
   cout << "Digite um numero: ";
   scanf("%d", &n);

   // Inicializa o começo da sequencia
   for(int i = 0; i < n; i++)
      sequencia += "0";

   for(int i = n; i < pow(2,n); i++)
   {
      subString = sequencia.substr(sequencia.length() - n + 1, n - 1);

      // Checa se a substring formada pelo os ultimos [n-1] da sequencia
      // mais o "1" se encontra nao se encontra na sequencia 
      if (sequencia.find(subString + "1") == string::npos)
         sequencia += "1";
      else
         sequencia += "0";
   }

   cout << "[WIKI]Sequencia de bruijn: " << sequencia << endl;
   printEspecial(sequencia, n);

   return 0;
}