题目内容

小红拿到了一个字符串，他希望通过切割操作将该字符串分割为完美字符串。完美字符串定义为长度大于等于2且首尾字符相同的串。

现在，小红想知道，在进行切割操作后，他所能得到的最多完美字符串的数量是多少？

输入描述

一个仅包含小写字母的字符串，长度不超过$200000$。

输出描述

如果无法切割且字符串本身不是完美字符串，请输出$-1$。

否则输出最终的完美字符串数量。

样例

输入输出示例仅供调试，后台数据一般不包含示例

输入

arcaea

输出

1

说明

本身即是完美字符串，且无法进行任何切制。

样例2

输入输出示例仅供调试，后台数据一般不包含示例

输入

abcb

输出

-1

说明

没有一种合法的切割方案。

https://www.bilibili.com/video/BV1N14y1R7R6

思路：动态规划

定义$dp[i]$为前i个字符的完美字符串的数量

定义前缀数组$pre[idx]$为以字符idx为结尾的最多完美字符串的数量。

从第2个字符开始，遍历字符串s。对于每个字符s[i]，我们有两种情况需要考虑：

• 第一种情况，如果s[i]等于s[1]，那么dp[i]就等于1，因为我们可以将s[1..i]作为一个完美字符串。
• 第二种情况，如果s[i]不等于s[1]，那么dp[i]就等于pre[s[i]] + 1，因为我们可以将s[1..pre[s[i]]]作为一个完美字符串，然后将s[pre[s[i]]+1..i]作为另一个完美字符串。