#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

从 S1S_1 开始,每一项都是下一项的前缀,因此可以把它们不断延伸到一条无限 Fibonacci 单词 SS。

给定一个只含 a、b 的字符串 tt。求最短的字符串 ss,满足:

  • ss 是无限 Fibonacci 单词 SS 的连续子串;
  • tt 是 ss 的子序列。

输出 ss 的最短长度。

输入格式

输入一行,包含一个长度在 11 到 150000150000 之间的 a/b 字符串 tt。

输出格式

输出一个整数,表示最短长度。

样例

输入:

aabbaab

输出:

8

长度不超过 7 的 Fibonacci 子串都不能包含 aabbaab 作为子序列;aababaab 可以,因此答案为 8。