CLR cover

Problem 63: Counting Factors by Length

\( \newcommand{\fac}{\mathit{fact}}% \newcommand{\prefixsum}{\mathit{prefix\_sum}}% \newcommand{\Count}{\mathit{Count}}% \)

Let $\fac_x[\ell]$ denote the number of (distinct) factors of length $\ell$ occurring in a word $x$.

Show how to compute in linear time all numbers $\fac_x[\ell]$, $\ell=1,\dots,|x|$, related to a word $x$, assuming a constant-size alphabet.
Exploit the Suffix tree of the word.