编译原理 3.4.9 题的解析与答案，特别是 4、5 题仅供参考。
题目：
Fibonacci 字符串的定义如下：
1) \(s1 = b\)
2) \(s2 = a\)
3) 当 \(k > 2\) 时， \(s_k = s_{k-1} s_{k-2}\)
例如：\(s3 = ab, s4 = aba, s5 = abaab\)
1) \(s_n\) 的长度是多少？
2) 构造 \(s_6\) 的失效函数。
3) 构造 \(s_7\) 的失效函数。
4) ! ! 说明任何 \(s_n\) 的失效函数都可以被表示为：\(f(1) = f(2) = 0\)，且对于 \(2 < j <= |s_n|, f(j) = j - |s_{k-1}|\)，其中 \(k\) 是使得 \(|s_k| <= j + 1\) 的最大整数。
5) ! ! 在 KMP 算法中，当我们试图确定关键字 \(s_k\) 是否出现在字符串 \(s_{k+1}\) 中，最多会连续多少次调用失效函数？
解答：
1) 根据 Fibonacci 字符串定义可知，\(|s_n| = |s_{n - 1}| + |s_{n - 2}|\)
2) 根据定义构造出 \(s_6 = abaababa\)，再根据失效函数定义写出对应位置的函数值即可，于是有：
| s | a | b | a | a | b | a | b | a |
|---|---|---|---|---|---|---|---|---|
| f(s) | 0 | 0 | 1 | 1 | 2 | 3 | 2 | 3 |
3) 与 2) 同理，有：
| s | a | b | a | a | b | a | b | a | a | b | a | a | b |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(s) | 0 | 0 | 1 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 6 | 4 | 5 |
4) 解释在下方。
5) 分为奇偶两种情形：
当 \(k > 4\) 时
其中 t 为最多连续回调次数。
解释：
4) 翻译并解释
使用数学归纳法能简单的得到 2 个定理：
定理 1：在 \(2 \leq k \leq n\) 时 \(s_n\) 总是以 \(s_k\) 作为前缀开头。特别的，当 \(n \geq 3\) 时，\(s_n\) 总是以 \(ab\) 开头。
定理 2：在 \(k \geq 3\) ，\(k\) 为奇， \(s_k\) 以 \(ab\) 结尾；否则以 \(ba\) 结尾。
定理 3：\(s_ks_{k-1}\) 和 \(s_{k-1}s_k\) 除最后两字符外，完全相等。并且在
\(k \geq 2\)时，两者最后两字符分别为 \(ab 或 ba\)。
证：
归纳基础：当 \(k = 2, s_2s_1 = ab, s_1s_2 = ba\) 时，它们是除最后两字符外相等的两个字符串。且最后两字符分别为 \(ab 或 ba\)。
归纳假设：当 \(k \geq 3，设\ \ s_{k-2}s_{k-1} \ \ 与 \ \ s_{k-1}s_{k-2}\) 仅最后两字符不等。于是有：
则 \(s_ks_{k-1} \) 和 \(s_{k-1}s_k\) 满足定理 3。
证毕。
定理 4：当 \(n \geq 3\) 时，\(s_n \) 具有失效函数 \(f\)。令 \(f(1) = f(2) = 0\)，当 \(2 < |s_k| - 1 \leq j \leq min(|s_n|, |s_{k+1}| - 2)\) 时，\(f(j) = j - |s_{k-1}|\).
能发现这与题目当中条件略有不同。
证：不失一般性，假设 \(n\) 足够大。据失效函数定义，\(f(1) = 0\)，又据定理 1，\(s_n\) 有前缀 \(ab\) 则 \(f(2) = 0\).
令 \(w[i]\) 表示字符串 \(w\) 第 \(i\) 字符，例如 \(w\) 表示 \(w[1], w[2], ..., w[strlen(w)]\) 的序列。
令 \(1 \leq x \leq |s_{k+1}| - |s_{k-1}| = |s_{k-1}| + |s_{k-2}| = |s_k|\).
由 \(s_n = s_k \ ...\ = s_{k-1}s_{k-2}\ ...\)，得 \(s_n[x] = (s_{k-1}s_{k-2})[x]\) ①
由 \(s_n = s_{k+1} \ ...\ = s_ks_{k-1}\ ...\ = \ (s_{k-1}s_{k-2})s_{k-1}\ ...\ = \ s_{k-1}(s_{k-2}s_{k-1})\)，得 \(s_n[|s_{k-1}| + x] = (s_{k-2}s_{k-1})[x]\). ②
由定理 3，当 \(x \leq |s_{k-1}| + |s_{k-2}| - 2\) 时，有 \(s_n[|s_{k-1}| + x] = |s_{k-1}| + |s_{k-2}|\) ③. 那么 \(|s_k| - 1 \leq j \leq |s_{k+1}| - 2\) 时，\(f(j) \geq j - |s_{k-1}|\).
①，② 示意图：
现在对 \(j\) 应用失效函数构造法，\(j + 1\) 使得 \(f(j) + 1\) 在该范围内始终成立。当 \(j = |s_{k+1}| - 1\) 时，\(f\) 增长不再为 \(1\) 因为：
不等原因来自定理 2，\(j - |s_{k-1}| \neq |s_{k-2}s_{k-1}| - 1\).即倒数第二位不等。
因此，由失效函数定义，此时\(j\)位置最大的 \(f(j)\) 可能为 \(f(f(j-1) + 1\).这是因为：$$f(f(j-1) + 1 = f(|s_k| - 2) + 1 = |s_{k-1}| - 1 = j - |s_k|. \quad ④$$
为什么最大的是\\((f(f(j-1) + 1\\)）？由上方示意图，当 \\(j\\) 处于\\(|s_{k+1} - 1|\\)，即 \\(s_{k+1}\\) 的倒数第二位，结合**定理 2**与失效函数构造算法即可。
由归纳假设法，对于 \(|s_{k+1}| - 1 \leq j \leq |s_{k+2}| - 2\)，由定理 4 得， \(f(j) \geq j - |s_k|\). 所以\(f(j) = |s_{k-1}| - 1 = j - |s_k|\)，这与我们 ④ 的结果一致。