Lyndon words: Duval's algorithm and its time complexity

[burritoloco]

Hi everyone,

Duval' algorithm computes all the k-ary Lyndon words up to any length, say n. See here for a brief introduction to Lyndon words and note the section Generation.

http://en.wikipedia.org/wiki/Lyndon_word

The article claims that
"the sequence of all Lyndon words of length at most n can be generated in time proportional to the length of the sequence" and cites this paper:

http://www-igm.univ-mlv.fr/~berstel/Articles/1994AverageCostDuval.pdf

Now, I have implemented Duval's algorithm for the binary case (see below) in C++ and noted that the computation time increases by a factor of almost 2 whenever the length of the sequence increases by 1. This starts becoming especially noticeable by about length 25. This I think would seem to suggest that the time complexity is actually exponential, which contradicts the claim of the linear complexity of the algorithm. As I'm not an expert in C++, I'm wondering if I'm implementing this incorrectly, or inefficiently. What do you think? Here's the algorithm.

In the binary case, i.e., k=2, Duval's algorithm simplifies to the following.

w[1] ← 0
i ← 1
repeat:
for j = 1 to n–i do
w[i+j] ← w[j]
/* at this point, w[1...i] is a Lyndon word */
i ← n
while i > 0 and w = 1
do i ← i–1
if i > 0 then w ← 1
until i = 0
end

You may find the algorithm in page 2 of this link as well:

http://ehess.modelisationsavoirs.fr/marc/publi/softcomputing/5000387periodicity.pdf

 

[burritoloco]

Here's my implementation:

#include<iostream>
#include<windows.h>

using namespace std;
int m;void duval(bool w[]);int main() {
cout << "Enter length of Lyndon word: ";
cin >> m;

bool *w = new bool[m+1];
DWORD startime = GetTickCount();
duval(w);
cout << "\nComputing time was " << (GetTickCount() - startime) << " milliseconds\n\n";
cin.get();
cin.get();
delete[] w;
return 0;
}

void duval(bool w[]) {
w[0] = 0;
w[1] = 0;

unsigned _int64 Nprim = 0;
int i=1;

do {

for(int j = 1; j <= m-i; j++) {
w[i+j] = w[j];
}

// At this point, w[1...i] is a Lyndon word

if(i == m) { // a Lyndon word of length m was found
Nprim++;

/*
for(int k=1; k <=m; k++) {
cout << w[k]; // print it
}
cout << endl;
*/
}

i = m;
while(i && w) {
i--;
}
if(i) {
w = 1;
}

} while(i);
cout << "\nNumber of Lyndon words is " << Nprim << endl;
}