Problem 139: Yet another application of suffix trees

$ \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.

125 Problems in Text Algorithms

Problem 139: Yet another application of suffix trees

References