# 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.