#
Problem 83: Counting Squares in Combs in Linear Time

\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\)

A comb is a labelled tree that consists of a path called the
*spine* with at most one *branch* attached to each
node of the spine.
All spine-edges are labelled with the letter $\sa{a}$.
Each branch is a path whose label starts with the letter
$\sa{b}$ followed by a number of $\sa{a}$'s.

The number of (distinct) squares occurring on branches of a comb $T$ can be
superlinear (see Problem 82) but despite the lower bound
it is possible to count them in linear time according to the tree size.
This is the goal of the problem.
This is done with a careful encoding of squares
due to their global structure.

Show how to compute in linear time the number of (distinct) square factors on
branches of a binary comb.

## References

T. Kociumaka, J. Pachocki, J. Radoszewski, W. Rytter, and T. Walen.
Efficient counting of square substrings in a tree. *Theor. Comput. Sci.*,
**544**:60-73, 2014.