```/******************************************************************************
* src/input/debruijn.h
*
* Algorithm to generate De Bruijn input sequences.
* extracted from FXT algorithm library http://www.jjj.de/fxt/fxtpage.html
*
******************************************************************************
* Original copyrighted by FXT algorithm library authors.
* Modifications copyright (C) 2012 Timo Bingmann <tb@panthema.net>
*
* This program is free software: you can redistribute it and/or modify it
* Software Foundation, either version 3 of the License, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
* more details.
*
* You should have received a copy of the GNU General Public License along with
* this program.  If not, see <http://www.gnu.org/licenses/>.
*****************************************************************************/

namespace debruijn {

// Generate necklaces, iterative algorithm.
class necklace
{
public:
ulong *a_;  // the string, NOTE: one-based
ulong *dv_; // delta sequence of divisors of n
ulong n_;   // length of strings
ulong m1_;  // m-ary strings, m1=m-1
ulong j_;   // period of the word (if necklaces)

public:
necklace(ulong m, ulong n)
{
n_ = ( n ? n : 1 );  // at least 1
m1_ = ( m>1 ? m-1 : 1); // at least 2
a_ = new ulong[n_+1];
dv_ = new ulong[n_+1];
for (ulong j=1; j<=n; ++j)  dv_[j] = ( 0==(n_%j ) );  // divisors
first();
}

~necklace()
{
delete [] a_;
delete [] dv_;
}

void first()
{
for (ulong j=0; j<=n_; ++j)  a_[j] = 0;
j_ = 1;
}

const ulong * data()  const  { return  a_ + 1; }

ulong next_pre()  // next pre-necklace
// return j (zero when finished)
{
// Find rightmost digit that can be incremented:
ulong j = n_;
while ( a_[j] == m1_ )  { --j; }

// Increment:
// if ( 0==j_ )   return 0;  // last
++a_[j];

// Copy periodically:
for (ulong k=j+1; k<=n_; ++k)  a_[k] = a_[k-j];

j_ = j;
return  j;
}

bool is_necklace()  const
{
return ( 0!=dv_[j_] );  // whether j divides n
}

bool is_lyn()  const
{
return ( j_==n_ );  // whether j equals n
}

ulong next()  // next necklace
{
do
{
next_pre();
if ( 0==j_ )  return 0;
}
while ( 0==dv_[j_] );  // until j divides n
return j_;
}

ulong next_lyn()  // next Lyndon word
{
do
{
next_pre();
if ( 0==j_ )  return 0;
}
while ( j_==n_ );  // until j equals n
return j_;  // == n
}
};

// Lexicographic minimal De Bruijn sequence.
class debruijn : public necklace
{
public:
ulong i_;   // position of current digit in current string

public:
debruijn(ulong m, ulong n)
: necklace(m, n)
{ first_string(); }

~debruijn()  { ; }

ulong first_string()
{
necklace::first();
i_ = 1;
return j_;
}

ulong next_string()  // make new string, return its length
{
necklace::next();
i_ = (j_ != 0);
return j_;
}

ulong next_digit()
// Return current digit and move to next digit.
// Return m if previous was last.
{
if ( i_ == 0 )  return necklace::m1_ + 1;
ulong d = a_[ i_ ];
if ( i_ == j_ )  next_string();
else  ++i_;
return d;
}

ulong first_digit()
{
first_string();
return next_digit();
}
};

template <typename Container>
void generate(int k, int n, Container& out)
{
debruijn deb(k,n);

if (pow(k,n) != out.size()) {
std::cout << "Length of de Bruijn sequence k=" << k << ", n = " << n << " is " << (int)pow(k,n) << "\n";
abort();
}

int i, o = 0;

while( (i = deb.next_digit()) != k )
{
out[o++] = (i + 1);
}
}

} // namespace debruijn
```