题目背景

下周你将主持一场声学流行歌曲大会，其中当然少不了卡拉 OK 之夜。为了给所有来宾留下深刻印象，你决定提前背下所有歌曲的歌词。

遗憾的是，歌词实在太长了。不过，你发现其中存在大量重复片段，于是决定先对歌词进行压缩，再记忆压缩后的内容。

题目描述

给定一个字符串 $s$。你必须选择 恰好一个 非空子串 $t$，并引入一个原字符串中从未出现过的新字符。

随后，在 $s$ 中选出尽可能多的、两两不重叠的 $t$ 的出现，并把每个被选中的出现整体替换成这个新字符，得到压缩后的字符串 $s'$。

为了还原歌词，你需要同时记住：

• 被替换的子串 $t$；
• 压缩后的字符串 $s'$。

因此总记忆长度为

求该总长度的最小可能值。

例如，在第一个样例中，字符串为 nanananananananabatman。

• 若选择 t = "na"，可以得到 XXXXXXXXbatman，总长度为 $2+14=16$；
• 若选择 t = "nana"，可以得到 XXXXbatman，总长度为 $4+10=14$，这是最优方案。

输入格式

输入一行一个字符串 $s$（$1\le |s|\le 5000$）。

字符串仅由小写英文字母 a–z 组成。

输出格式

输出一个整数，表示 $|t|+|s'|$ 的最小值。

样例 1

输入

nanananananananabatman

输出

14

样例 2

输入

abcabd

输出

6

样例 3

输入

nocompression

输出

14

难度评定

预计 Codeforces 难度：2400。

核心知识点为字符串哈希、全部子串的增量枚举和相同子串的非重叠出现计数。需要把朴素的 $O(n^3)$ 或 $O(n^4)$ 做法压到 $O(n^2)$，并在约 $1.25\times10^7$ 个子串状态下控制常数和内存。哈希碰撞、键中必须包含长度、非重叠贪心更新以及 64 位运算都是高风险实现点。