#P5918. [Usaco2023 Open] Pareidolia S
[Usaco2023 Open] Pareidolia S
题目描述
Farmer John 常在日常事物中看出奶牛的影子。例如,他会忽略 bqessiyexbesszieb 中的一些字母,只看到 bessiebessie。
对字符串 ,定义 为从 中删除零个或多个字符后,剩余部分恰好由若干个 bessie 首尾拼接而成时,能保留的最多副本数。上面的例子中 。
给定字符串 ,对它的每个非空连续子串 计算 ,求这些值的和。子串按在 中的起止位置分别计数。
输入格式
输入一个非空字符串 ,仅含小写英文字母,长度不超过 。
输出格式
输出一个整数,表示所有子串的 之和。
样例 #1
样例输入 #1
bessiebessie
样例输出 #1
14
样例解释 #1
有 12 个子串的 为 1,一个子串的 为 2,故答案是 。
样例 #2
样例输入 #2
abcdefghssijebessie
样例输出 #2
28
测试点性质
- 测试点 3–5 的字符串长度不超过 5000。
- 测试点 6–12 无额外限制。