CLR cover

Additional Problem 17: Yet another application of suffix trees

\( \def\dd{\dot{}\dot{}} \def\Sub{\mathsf{Sub}} \def\weight{\mathsf{weight}} \)

We show how the suffix tree can be used in three different ways to solve an example problem. For a string $w = w[0\dd n-1]$ denote by $\Sub[k]$ the number of distinct nonempty subwords of $w$ having an occurrence starting in the interval $[0,k]$. Assume (for simplicity) that $w$ ends with a unique symbol (endmarker).

Given the suffix tree $T$ of $w$. Design a simple algorithm working in $O(n)$ time, which computes the table $\Sub[0\dd n-1]$.

Let $\weight(u)$ be the length of the word corresponding to a node $u$. The weight of an edge is the absolute value of the difference between the end-nodes of this edge.

References

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