The word $\sa{cbcbacbcbacbc}=(\sa{cbcba})^2\sa{cbc}$ is self-maximal as well as its prefix period $\sa{cbcba}$ that is additionally border free. Its suffix $\sa{cbcba}\sa{cbc}$ is essentially the only suffix competing with it as the greatest suffix. A letter $a$ appended to it is then to be compared to the letter following the prefix occurrence of $\sa{cbcba}\sa{cbc}$.

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.

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