#2034. [USACO23OPEN] Pareidolia S

[USACO23OPEN] Pareidolia S

题目描述

给定一个字符串 ss,令 B(s)B(s) 表示通过删除 ss 中的零个或多个字符后,能够形成的 "bessie" 的最大重复次数。在上面的例子中,B(“bqessiyexbesszieb")=2B(\text{``bqessiyexbesszieb"}) = 2。

计算 B(s)B(s) 是一个有趣的挑战,但农夫 John 对解决一个更有趣的挑战感兴趣:给定一个长度不超过 3⋅1053 \cdot 10^5 的字符串 tt,且仅由字符 a-z 组成,计算所有连续子串 ss 的 B(s)B(s) 之和。

输入格式

输入由一个非空字符串组成,长度不超过 3⋅1053 \cdot 10^5,且所有字符均为小写英文字母。

输出格式

输出一个数字,表示输入字符串的所有子串中能够形成的 "bessie" 的总数。

样例

bessiebessie
14
abcdefghssijebessie
28

题目来源:洛谷 P9188