CLR cover

Problem 29: Strict Border Table of the Fibonacci Word

\( \def\tbord{\mathit{border}} \def\sbord{\mathit{stbord}} \def\tper{\mathit{period}} \def\dd{\dot{}\dot{}} \def\sa#1{\tt{#1}} \)

The border table $\tbord$ (see Problem 19) of the infinite Fibonacci word $\mathbf{f}$ has a simple structure but values in its strict border table $\sbord$ (see Problem 25) look chaotic at first glance. The problem examines a simple relation between the two tables, which helps to quickly compute any individual value of the table $\sbord$.

Below are the tables of periods, borders and strict borders related to a prefix of the Fibonacci word. Values at index $\ell$ correspond to the prefix $\mathbf{f}[0\dd \ell-1]$ of length $\ell$.
$i$ 012345678910
$x[i]$ $\sa{a}$$\sa{b}$$\sa{a}$$\sa{a}$$\sa{b}$$\sa{a}$$\sa{b}$$\sa{a}$$\sa{a}$$\sa{b}$$\sa{a}$
$\ell$ 01234567891011
$\tper[\ell]$ 12233355555
$\tbord[\ell]$ -10 011 23 234 56
$\sbord[\ell]$ -10-110-13-110-16

Show how to compute in logarithmic time the $n$th element of the strict border table of the infinite Fibonacci word $\mathbf{f}$.
Examine positions where tables $\tbord$ and $\sbord$ match.