CLR cover

Problem 40: Maximal Suffix and Its Period

The maximal suffix of a word is its alphabetically greatest suffix. The problem follows Problem 38 and presents another pseudo-code for computing a maximal suffix. As the other it processes its input in linear time using only constant extra space.

MaxSuffixPP$(x \mbox{ non-empty word})$ 
    \begin{algorithmic}
\STATE $(ms,j,p,k)\leftarrow (0,1,1,0)$
\WHILE{$j+k \lt |x|$}
    \IF{$x[j+k] \gt x[ms+k]$}
        \STATE $(ms,j,p,k)\leftarrow (j,j+1,1,0)$
    \ELSEIF{$x[j+k] \lt x[ms+k]$}
        \STATE $(j,p,k)\leftarrow (j+k+1,j-ms,0)$
    \ELSEIF{$k = p-1$}
        \STATE $(j,k)\leftarrow (j+k+1,0)$
    \ELSE
        \STATE $\leftarrow k+1$
    \ENDIF 
\ENDWHILE
\RETURN{$(ms,p)$}
    \end{algorithmic}

Show that Algorithm MaxSuffixPP computes the starting position and the period of the maximal suffix of its input word.

Show how to test the primitivity of a word in linear time and constant extra space.

References

  • M. Crochemore and D. Perrin. Two-way string-matching. J. ACM, 38(3):651-675, 1991.