#6288. 猫咪

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: BigFairyNBC

题目描述

原题来自:Codeforces Round #364 (Div. 1) E

大 F 想养猫。

“你喜欢小猫咪吗?”
“喵。”
“你变成猫了吗?”
“喵!”

大 F 喜欢小猫咪,大 F 想养很多很多小猫咪,但是大 F 的想象力十分匮乏,她希望小 F 来帮她为猫咪们取名字。

小 F 也喜欢小猫咪,小 F 也想养许多许多小猫咪,但是小 F 有强迫症,如果养了 K 只猫咪,名字分别是非空字符串 S_1, S_2, \ldots S_K ,她希望对于所有的 2 \le i \le K S_i S_{i-1} 双子串。另外,小 F 还希望 S_1 是她自己给定的字符串 T 子串

诶,我们刚刚提到了双子串。字符串 A 被称作 B 双子串,意思是说, A 作为 B 的子串,在 B 中的不同位置出现了至少 2 。比如说, ABCZZABCZZABCZZ 的双子串, ABAABABA 的双子串(这里的两次出现有重叠部分,这是允许的),而 AAB 不是 AABAB 的双子串。

小 F 想养尽量多的猫咪,所以小 F 想要找到尽量大的 K ,使得存在 S_1, S_2, \ldots, S_K 满足条件。

输入格式

一行一个字符串 T ,仅含小写字母。

输出格式

一个整数,可能的 K 的最大值。

样例

样例输入 1

qaqaqzz

样例输出 1

3

样例解释 1

S_1= qaqaqzz

S_2= qaq

S_3= q

样例输入 2

dabcabcabcabca

样例输出 2

5

样例解释 2

S_1= abcabcabcabca

S_2= abcabcabca

S_3= abcabca

S_4= abca

S_5= a

样例输入 3

abracadabra

样例输出 3

3

样例解释 3

S_1= abracadabra

S_2= abra

S_3= a

数据范围与提示

对于所有数据,保证 1 \le N = \left| T\right| \le 2\times 10^5 S 仅含小写字母。

下表为各个 Subtask 的额外限制与得分,空格表示该项无额外限制。你只有通过一个 Subtask 的所有数据才能得到该 Subtask 的分。

Subtask 编号 N 特殊限制 分值
1 \le 50 5
2 \le 4000 24
3 K 取到最大值时,存在一种 S_{1\ldots K} 的取法使得对于所有 1\le i \le K S_i 都是 T 的前缀 17
4 54