题目内容

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

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

思路：动态规划

定义$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]作为另一个完美字符串。