CLR cover

Problem 38: Simple Maximal Suffix Computation

The maximal suffix of a word is its alphabetically greatest suffix. The notion is a key element in some combinatorial aspects of words (e.g. related to runs or critical positions) but also in the development of string-matching algorithms (e.g. the two-way algorithm used in some C libraries such as glibc and FreeBSD's lib). The algorithm presented in this problem is tricky but simpler than the one in Problem 40. Both work in place, that is, need only constant space to work in addition to their input (contrary to the solution in Problem 23), which makes their implementation straightforward.

For a non-empty word $x$, Algorithm MaxSuffixPos computes the starting position of $\MS(x)$, maximal suffix of $x$.

Note the similarity between MaxSuffixPos and Algorithm CyclicEquivalence in Problem 37 and the similarity of its pseudo-code with that of the other version in Problem 40.

MaxSuffixPos$(x \textrm{ non-empty word})$ 
    \begin{algorithmic}
  \STATE $(i,j)\leftarrow (0,1)$
  \WHILE{$j\lt |x|$}
    \COMMENT{note the invariant $i\lt j$}
    \STATE $k\leftarrow 0$
    \WHILE{$j+k\lt |x| \mbox{ and } x[i+k] = x[j+k]$}
      \STATE $k\leftarrow k+1$
    \ENDWHILE
    \IF{$j+k=|x| \mbox{ or } x[i+k] \gt x[j+k]$}
      \STATE $j\leftarrow j+k+1$
    \ELSE
      \STATE $i\leftarrow i+k+1$
    \ENDIF
    \IF{$i\geq j$}
      \STATE $j\leftarrow i+1$
    \ENDIF
  \ENDWHILE
  \RETURN{$i$}
    \end{algorithmic}

Show that Algorithm MaxSuffixPos computes the position on a word of its maximal suffix and that it runs in linear time with constant extra space.

References

  • Z. Adamczyk and W. Rytter. A note on a simple computation of the maximal suffix of a string. J. Discrete Algorithms, 20:61-64, 2013.