#P18132. Pattern Search II
Pattern Search II
Pattern Search II
定义 Fibonacci 单词序列:
$$S_0=\texttt{b},\quad S_1=\texttt{a},\quad S_i=S_{i-1}S_{i-2}\quad(i\ge2).$$前几项为:
S0 = b
S1 = a
S2 = ab
S3 = aba
S4 = abaab
S5 = abaababa
S6 = abaababaabaab
从 开始,每一项都是下一项的前缀,因此可以把它们不断延伸到一条无限 Fibonacci 单词 。
给定一个只含 a、b 的字符串 。求最短的字符串 ,满足:
- 是无限 Fibonacci 单词 的连续子串;
- 是 的子序列。
输出 的最短长度。
输入格式
输入一行,包含一个长度在 到 之间的 a/b 字符串 。
输出格式
输出一个整数,表示最短长度。
样例
输入:
aabbaab
输出:
8
长度不超过 7 的 Fibonacci 子串都不能包含 aabbaab 作为子序列;aababaab 可以,因此答案为 8。