Problem 42: Periods of Lyndon Word Prefixes

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\tper{\mathit{period}} $

A Lyndon word is a non-empty self-minimal word, that is, it is alphabetically smaller than all its non-empty proper suffixes. The dual self-maximal words share some of their features. Lyndon words have useful properties for the design of matching algorithms and for the analysis of methods such as testing the cyclic equivalence of two words (Problem 37). The present problem deals with a remarkable simple solution to compute their prefix periods.

Let $\tper$ denote the table of periods of prefixes of the word $x$. It is defined on non-empty prefix lengths $\ell$, $\ell=1,\dots,|x|$, by $$\tper[\ell] = \mbox{ smallest period of } x[0\dd \ell-1].$$ For the word $x = \sa{aabababba}$ we get

$i$ 0 1 2 3 4 5 6 7 8

$x[i]$ $\sa{a}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{b}$ $\sa{b}$ $\sa{a}$

$\ell$ 1 2 3 4 5 6 7 8 9

$\tper[\ell]$ 1 1 3 3 5 5 7 8 8

Show that Algorithm PrefixPeriods correctly computes the table of periods of prefixes of a Lyndon word.

PrefixPeriods$(x \textrm{ Lyndon word})$

    \begin{algorithmic}
\STATE $period[1]\leftarrow 1$
\STATE $p\leftarrow 1$
\FOR{$\ell\leftarrow 2$ \TO $|x|$} 
    \IF{$x[\ell-1] \neq x[\ell-1-p]$}
        \STATE $p\leftarrow \ell$
    \ENDIF
    \STATE $period[\ell]\leftarrow p$
\ENDFOR
\RETURN{$period$}
    \end{algorithmic}

What changes are to be made to PrefixPeriods to compute the prefix periods of a self-maximal word?

Show that testing if a word is a Lyndon word can be done in linear time with only constant extra space.

Tune Algorithm PrefixPeriods.

125 Problems in Text Algorithms

Example

Problem 42: Periods of Lyndon Word Prefixes

References

$i$	0	1	2	3	4	5	6	7	8
$x[i]$	$\sa{a}$	$\sa{a}$	$\sa{b}$	$\sa{a}$	$\sa{b}$	$\sa{a}$	$\sa{b}$	$\sa{b}$	$\sa{a}$
$\ell$	1	2	3	4	5	6	7	8	9
$\tper[\ell]$	1	1	3	3	5	5	7	8	8