#P5918. [Usaco2023 Open] Pareidolia S

    ID: 4918 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 6 上传者: 标签>难度分类普及+/提高-动态规划自动机 DP贪心贪心保持领先状态维度消除滚动数组CF1900

[Usaco2023 Open] Pareidolia S

题目描述

Farmer John 常在日常事物中看出奶牛的影子。例如,他会忽略 bqessiyexbesszieb 中的一些字母,只看到 bessiebessie。

对字符串 ss,定义 B(s)B(s) 为从 ss 中删除零个或多个字符后,剩余部分恰好由若干个 bessie 首尾拼接而成时,能保留的最多副本数。上面的例子中 B(s)=2B(s)=2。

给定字符串 tt,对它的每个非空连续子串 ss 计算 B(s)B(s),求这些值的和。子串按在 tt 中的起止位置分别计数。

输入格式

输入一个非空字符串 tt,仅含小写英文字母,长度不超过 3×1053\times10^5。

输出格式

输出一个整数,表示所有子串的 B(s)B(s) 之和。

样例 #1

样例输入 #1

bessiebessie

样例输出 #1

14

样例解释 #1

有 12 个子串的 B(s)B(s) 为 1,一个子串的 B(s)B(s) 为 2,故答案是 12⋅1+1⋅2=1412\cdot1+1\cdot2=14。

样例 #2

样例输入 #2

abcdefghssijebessie

样例输出 #2

28

测试点性质

  • 测试点 3–5 的字符串长度不超过 5000。
  • 测试点 6–12 无额外限制。