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.