#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// Toggle debug
#define DEBUG_SEARCH

template<typename Iter>
void print(Iter a, Iter b)
{
   for( Iter i=a; i!=b; ++i )
      cout << *i;
   cout << endl;
}

//
// Compares two sequences of equal length
// Note: there may be an STL function that already does this
//
template<typename Iter>
bool search_at( Iter current, Iter begsub, unsigned int n )
{

#ifdef DEBUG_SEARCH
cout << "search for";
print(begsub,begsub+n);
cout << "in ";
print(current,current+n);
#endif

   if ( search(current,current+n,begsub,begsub+n)!=current )
   {

#ifdef DEBUG_SEARCH
cout << "beg to seachresult";
print(begsub,search(begsub,begsub+n,current,current+n));
#endif

      return false;
   }

   return true;
}
   

void test01()
{
   int a[] = {1,0,1,0, 1,1,1,1, 1,0,1,0, 1,1,1,1};
   vector<int> v(a,a+sizeof(a)/sizeof(int));
 
   cout << "Sequence: ";
   print(v.begin(),v.end());
   cout << endl;

   cout << search_at(v.begin()+2,v.begin(),2) << endl;
   cout << search_at(v.begin()+8,v.begin(),4) << endl;
}


//
// Algorithm: Finds cyclic nature of sequence
// The cycle must be repeated at least once
// Chelton Evans, Sunday 28th April 2002
//
template<typename Iter>
unsigned int period_search( Iter beg, Iter end )
{
   // Trivial cases
   if (beg==end)
      return 0;
   if (beg+1==end)
      return 1;

   unsigned int n = (end-beg);
   unsigned int periodmax = (n-(n%2))/2;

#ifdef DEBUG_SEARCH
cout << "periodmax=" << periodmax << endl;
#endif

   for (unsigned int period=1; period<=periodmax; ++period)
   {
      for (Iter current=beg; ; current += period)
      {
         if (current+period < end)
         {

#ifdef DEBUG_SEARCH
cout << "# current+period < end" << endl;
#endif

            if (search_at(current,beg,period))
               continue;

            break;
         }
         if (end < current+period)
         {

#ifdef DEBUG_SEARCH
cout << "@ end < current+period" << endl;
#endif

            if (search_at(current, beg, end-current))
               return period;
           
            break;
         }
         
         // current+period == end
         {

#ifdef DEBUG_SEARCH
cout << "$ current+period == end" << endl;
#endif

            if(search_at(current,beg,period))
               return period;

            break;
         }
      }
   }

   return 0;
}
      

void test02()
{
   //int a[] = {1,0,1,0, 1,1,1,1, 1,0,1,0, 1,1,1,1};
   //int a[] = {1,1,1,1};
   //int a[] = { 2,1,2,1 };
   int a[] = {1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 
 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1};
   vector<int> v(a,a+sizeof(a)/sizeof(int));

   cout << "Sequence: ";
   print(v.begin(),v.end());
   cout << endl;

   unsigned int k;
   k = period_search(v.begin(),v.end());
   cout << "k=" << k;

}
   
  
   

int main()
{
   test02();
  
   return 0;
}