Skip to content

Instantly share code, notes, and snippets.

@resilar
Created June 15, 2016 14:23
Show Gist options
  • Save resilar/bca44568a7aa7fc42aa3d5500976dbe3 to your computer and use it in GitHub Desktop.
Save resilar/bca44568a7aa7fc42aa3d5500976dbe3 to your computer and use it in GitHub Desktop.
Lyndon factorization
/**
* Compute the Lyndon factorization of S[0..n-1].
* O(n) time and O(1) space blabla.
*
* ... because Duval's algorithm is a piece of shit.
*/
void lyn(unsigned char *S)
{
int u, v;
u = v = 0;
while (S[v++]) {
for (u = 0; S[u+v] == S[u]; u++);
if (S[u+v] < S[u]) {
v = v * (1 + u/v);
printf("%.*s.", v, S);
S = &S[v]; v = 0;
} else {
v = v + u;
}
}
printf("\n");
}
/* note: commenting L14 toggles standard factorization, */
/* i.e., "abcabc.a." <=> "abc.abc.a." */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment