CLR cover
Previous problem

Problem 139: Yet another application of suffix trees

Next problem
\( \def\dd{\dot{}\dot{}} \def\Sub{\mathit{Sub}} \)

In this problem, we show how the Suffix tree of a word can be used in three different ways to solve an example problem. For a string $x$, let $\Sub[k]$ denote the number of (distinct) nonempty factors of $x$ having an occurrence whose position starts in the interval $[0\dd k]$. For simplicity, assume that $x$ ends with a unique symbol.

Show how to compute the table $\Sub[0\dd n-1]$ in linear time.

Use a suffix tree.

References

  • E. M. McCreight. A space-economical suffix tree construction algorithm. J. ACM, 23(2):262-272, 1976.