Problem 23: Border Table to Maximal Suffix

$ \def\ms{\mathit{ms}} \def\sa#1{\tt{#1}} \def\tbord{\mathit{border}} \def\MS{\mathrm{MaxSuffix}} $

The maximal suffix of a word, its alphabetically greatest suffix, helps designing optimal text searches and periodicity tests. The problem introduces a computation of it based on the border table algorithm.

Show that the following version of the border table computation correctly returns the starting position on the input word of its maximal suffix and that it runs in linear time.

MaxSuffixPos$(x \mbox{ non-empty word})$

    \begin{algorithmic}
\STATE $ms \leftarrow 0$
\STATE $border[0] \leftarrow -1$
\FOR{$i \leftarrow 0$ \TO $|x|-1$}
    \STATE $\ell \leftarrow border[i-ms]$
    \WHILE{$\ell\geq 0$ \AND $x[ms+\ell]\neq x[i]$}
        \IF{$x[ms+\ell] \lt x[i]$}
            \STATE $ms \leftarrow {i-\ell}$
        \ENDIF 
        \STATE $\ell \leftarrow border[\ell]$
    \ENDWHILE
    \STATE $border[i-ms+1] \leftarrow \ell+1$
\ENDFOR
\RETURN $ms$
    \end{algorithmic}

Example

The word $x=\sa{abcbcacbc}$ has maximal suffix $\MS(x)=\sa{cbcacbc}$ whose longest border is $v=\sa{cbc}$. A next letter is to be compared with the letter following the prefix $\sa{cbc}$ of the maximal suffix.

The following pictures show how the maximal suffix evolves according to the appended letter $\sa{a}$, $\sa{b}$, $\sa{c}$ or $\sa{d}$. Note that if the periodicity of the maximal suffix changes, the maximal suffix is of the form $va$ where $v$ is a border of the initial maximal suffix and $a$ is the new letter.

Show how to find the alphabetically largest conjugate (rotation) of a word.

References

K. S. Booth. Lexicographically least circular substrings. Inf. Process. Lett., 10(4/5):240-242, 1980.

125 Problems in Text Algorithms

Example

Border Table to Maximal Suffix

Problem 23: Border Table to Maximal Suffix

Example

References