CLR cover

Problem 39: Self-Maximal Words

The notion of a self-maximal word, word that is the alphabetically greatest among its suffixes, is somehow dual to the notion of Lyndon word, word that is smaller than all its proper non-empty suffixes. The former words appear naturally when locating critical positions on a word (see Problem 41) and in string-matching algorithms based on them.

Algorithm SelfMaximal checks if its input word $x$ is self-maximal, that is, if $x=\MS(x)$. It processes the word in real time because the instruction in the for loop executes in constant time.

SelfMaximal$(x \mbox{ non-empty word})$ 
    \begin{algorithmic}
\STATE $p\leftarrow 1$
\FOR{$i \leftarrow 1$ \TO $|x|-1$}
    \IF{$x[i] \ge x[i-p]$}
        \RETURN{\False}
    \ELSEIF{$x[i] \le x[i-p]$}
        \STATE $p\leftarrow i+1$
    \ENDIF
\ENDFOR
\RETURN{\True}
    \end{algorithmic}

Prove that the above really simple algorithm correctly tests if its input word is greater than all its proper suffixes.

The next picture illustrates the role of variables in SelfMaximal.

Self Maximal

Upgrade the above algorithm to SMPrefix that computes the longest self-maximal prefix of a word.

References

  • J. Duval. Factorizing words over an ordered alphabet. J. Algorithms, 4(4):363-381, 1983.