CLR cover
Previous problem

Problem 83: Counting Squares in Combs in Linear Time

Next problem
\( \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.