D-回文字D_牛客练习赛79

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

死宅hx特别喜欢《头文字D》这部动漫，“逮虾户”神曲是他刷题和比赛时的必听曲目之一。因此，hx发明了一种 $D$ 型回文串。假如字符串长度为 $m$ ，若满足以下两个条件之一，该字符串就为 $D$ 型回文串。

1：假如 $m<D$ ，则该字符串为 $D$ 型回文串（并不要求这个字符串为回文串）。

2：假如 $m\geq D$ ，且该字符串中任意一个长度为 $D$ 的子串均为回文串，则该字符串为 $D$ 型回文串。

定义字符串的拼接操作符为 $+$ ， $S+T$ 表示将字符串 $T$ 接到 $S$ 后面，例如 $aa+bb=aabb$ 。现给你一个长度为 $n$ 且均为小写字母的字符串 $S$ ，你可以任意划分 $S$ ，使得 $S=S_{1}+S_{2}+...+S_{k}$ 。在满足 $S_{1},S_{2},...,S_{k}$ 均为 $D$ 型回文串的条件下，请你告诉hx最小的 $k$ 是多少。