Lyndon factorization

lyn.c

/**
 * 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." */