Generating Lyndon words of length n | C ++ implementation of the above approach ; To store the indices of the characters ; Loop till w is not empty ; Incrementing the last character ; Repeating w to get a n - length string ; Removing the last character as long it is equal to the largest character in S
#include <bits/stdc++.h> NEW_LINE using namespace std ; int main ( ) { int n = 2 ; char S [ ] = { '0' , '1' , '2' } ; int k = 3 ; sort ( S , S + 3 ) ; vector < int > w ; w . push_back ( -1 ) ; while ( w . size ( ) > 0 ) { w [ w . size ( ) - 1 ] ++ ; int m = w . size ( ) ; if ( m == n ) { string str ; for ( int i = 0 ; i < w . size ( ) ; i ++ ) { str += S [ w [ i ] ] ; } cout << str << endl ; } while ( w . size ( ) < n ) { w . push_back ( w [ w . size ( ) - m ] ) ; } while ( w . size ( ) > 0 && w [ w . size ( ) - 1 ] == k - 1 ) { w . pop_back ( ) ; } } return 0 ; }