De Bruijn sequence | Set 1 | C ++ implementation of the above approach ; Modified DFS in which no edge is traversed twice ; Function to find a de Bruijn sequence of order n on k characters ; Clearing global variables ; Number of edges ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_set < string > seen ; vector < int > edges ; void dfs ( string node , int & k , string & A ) { for ( int i = 0 ; i < k ; ++ i ) { string str = node + A [ i ] ; if ( seen . find ( str ) == seen . end ( ) ) { seen . insert ( str ) ; dfs ( str . substr ( 1 ) , k , A ) ; edges . push_back ( i ) ; } } } string deBruijn ( int n , int k , string A ) { seen . clear ( ) ; edges . clear ( ) ; string startingNode = string ( n - 1 , A [ 0 ] ) ; dfs ( startingNode , k , A ) ; string S ; int l = pow ( k , n ) ; for ( int i = 0 ; i < l ; ++ i ) S += A [ edges [ i ] ] ; S += startingNode ; return S ; } int main ( ) { int n = 3 , k = 2 ; string A = "01" ; cout << deBruijn ( n , k , A ) ; return 0 ; }