Failure function of the Fibonacci strings (The Dragon Book Exercise 3.4.9d)

Question

Exercise 3.4.9 of The Dragon Book defines Fibonacci strings as follows:

1. $s_1 = b$.
2. $s_2 = a$.
3. $s_k = s_{k-1}s_{k-2}$ for $k>2$.

Part (d) then poses the following question:

Show that the failure function of $s_n$ can be expressed by $f(1) = f(2) = 0$, and for $2 < j \le |s_n|$, $f(j)$ is $j - |s_{k-1}|$ where $k$ is the largest integer such that $|s_k| \le j + 1$.

For avoidance of doubt, the failure function $f$ of a string $b_1b_2\ldots{}b_n$ is defined for integer values $i$ satisfying $1 \le i \le n$ in order that $b_1b_2\ldots{}b_{f(i)}$ is the longest proper prefix of $b_1b_2\ldots{}b_i$ that is also a suffix of the latter. Thus $f(i)$ is the length of the longest proper prefix of $b_1b_2\ldots{}b_i$ that is a suffix of $b_1b_2\ldots{}b_i$ also.

I have struggled for a long time and cannot see how to solve this question: can anyone explain this? I can see that the failure function of $s_{n-1}$ will be identical with that of $s_n$ until $j > |s_{n-1}|$ but beyond this I have not managed.

Answer 1

It is easy to use straightforward induction to prove the following two claims.

Claim One: $s_n$ starts with $s_k$ for $2\le k\le n$. In particular, $s_n$ starts with $ab$ for $n\ge3$.

Claim Two: $s_k$ ends with either $ab$ when $k$ is odd or $ba$ when $k$ is even for $k\ge3$.

---

Claim Three: $s_ks_{k-1}$ and $s_{k-1}s_k$ are the same except the last two letters, which are either $ab$ or $ba$ for $k\ge2$.

Proof: For $k=2$, $s_2s_1=ab$ and $s_1s_2=ba$ are the same except the last two letters, which are either $ab$ or $ba$.

Suppose $k\ge3$.
$s_ks_{k-1}=(s_{k-1}s_{k-2})s_{k-1}=s_{k-1}(s_{k-2}s_{k-1}).$
$s_{k-1}s_k=s_{k-1}(s_{k-1}s_{k-2})$
Thanks to induction hypothesis that says $s_{k-2}s_{k-1}$ and $s_{k-1}s_{k-2}$ are the same except the last two letters, which are either $ab$ and $ba$, so are $s_ks_{k-1}$ and $s_{k-1}s_k$.

---

Claim Four: Let $f$ be the failure function of $s_n$, $n\ge3$. Then $f(1)=f(2)=0$ and for $2\lt|s_k|-1\le j\le \min(|s_n|, |s_{k+1}|-2)$, we have $f(j)=j-|s_{k-1}|$.

Note that Claim Four is Exercise 3.4.9 stated in a slightly different way.

Proof: WLOG, suppose $n$ is large enough, thanks to Claim One.
$f(1)=0$ by definition.
Since $s_n$ starts with $ab$, $f(2)=0$.

Let $w[i]$ mean the $i$-th letter of string $w$, i.e., $w$ is the sequence $w[1]$, $w[2]$, $\cdots$, $w[\text{length of }w]$.

Let $1\le x\le |s_{k+1}|-|s_{k-1}|=|s_{k-1}| + |s_{k-2}|$.
Since $s_n = s_k\cdots =s_{k-1}s_{k-2}\cdots$, we have $s_n[x] = (s_{k-1}s_{k-2})[x]$.
Since $s_n= s_{k+1}\cdots = s_ks_{k-1}\cdots=(s_{k-1}s_{k-2})s_{k-1}\cdots=s_{k-1}(s_{k-2}s_{k-1})\cdots$, we have $s_n[|s_{k-1}|+x]=(s_{k-2}s_{k-1})[x]$.

Thanks to Claim Three, we have $s_n[x] = s_n[|s_{k-1}|+x]$ if $x\le|s_{k-1}| + |s_{k-2}|-2$, which implies $f(j)\ge j-|s_{k-1}|$ for $|s_k|-1\le j\le |s_{k+1}|-2$.

Now we can apply the standard algorithm that builds this failure function $f$ of KMP algorithm, where the base cases are easy and the length of match $f(j)$ always increases by $1$ when $j$ increases by $1$, unless at the time when $j$ increases to $|s_{k+1}|-1$ for some $k$, as shown above.

At that time when $j$ increases to $|s_{k+1}|-1$, $f(\cdot)$ does not increase by $1$ since $$\begin{aligned} s_n[j-|s_{k-1}|]&=(s_{k-1}s_{k-2})[j-|s_{k-1}|]\\ &\not=(s_{k-2}s_{k-1})[j-|s_{k-1}|]\\ &= s_n[(j-|s_{k-1}|)+ |s_{k-1}|]\\ &=s_n[j], \end{aligned}$$ where the inequality comes from Claim Two as $j-|s_{k-1}|=|s_{k-2}s_{k-1}|-1$.

Hence, by the nature of the failing function, the most $f(j)$ could be is $f(f(j-1))+1$. Thanks to the induction hypothesis, $$f(f(j-1))+1=f(|s_k|-2|)+1= |s_{k-1}|-1=j-|s_k|.$$ Since $|s_{k+1}|-1\le j\le |s_{k+2}|-2$, we have proved above that $f(j)\ge j-|s_k|$. Hence $f(j)=|s_{k-1}|-1=j-|s_{k}|$ as wanted. $\quad\checkmark$.