CLR cover
Previous problem

Problem 104: Compressed Matching in the Fibonacci Word

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\fib{\mathit{fib}} \)

Compressed matching refers to the following problem: given compact representations of a pattern and of a text, locate the pattern in the text in a fast manner according to their compressed representations. The representation sizes can be logarithmic with respect to the real input sizes, as it takes place in this problem example.

The input depends on the type of compressed representation. Here we consider a very simple case where the pattern is specified as a concatenation of Fibonacci words and its representation is the sequence of their indices. The searched text is the infinite Fibonacci word $\mathbf{f}=\phi^{\infty}(\sa{a})$, where $\phi$ is the morphism defined by $\phi(\sa{a})=\sa{ab}$ and $\phi(\sa{b})=\sa{a}$.

The word $\sa{b}$ is added with index $-1$ to the list of Fibonacci words: $\fib_{-1}=\sa{b}$, $\fib_0=\sa{a}$, $\fib_1=\sa{ab}$, $\fib_2=\sa{aba}$, $\fib_3=\sa{abaab}$, \dots

Given a sequence of integers $k_1,k_2,\ldots, k_n$ ($k_i\geq-1$) show how to check in time $O(n+k_1+k_2+\cdots+k_n)$ if $\fib_{k_1}\fib_{k_2}\cdots\fib_{k_n}$ occurs in the infinite Fibonacci word $\mathbf{f}$.

References

  • B. Walczak. A simple representation of subwords of the Fibonacci word. Inf. Process. Lett., 110(21):956-960, 2010.