Pareidolia

题目描述

注意：本题时间限制为 4s，是默认时间限制的 2 倍。

空想性错视（Pareidolia）是一种现象：你的眼睛倾向于在并不存在熟悉图案的图像中看到熟悉的模式——例如在云朵里看到一张脸。可以想象，由于 Farmer John 经常和奶牛待在一起，他常常会在日常物体中看到与奶牛相关的模式。例如，当他看字符串 "bqessiyexbesszieb" 时，Farmer John 的眼睛会忽略其中一些字母，而他看到的只有 "bessiebessie"。

给定一个字符串 $s$，令 $B(s)$ 表示：通过从 $s$ 中删除零个或多个字符，最多可以形成多少个重复的 "bessie"。在上面的例子中，$B($"bqessiyexbesszieb"$) = 2$。

计算 $B(s)$ 本身就是一个有趣的挑战，但 Farmer John 想解决一个更有趣的挑战：给定一个长度至多为 $3\cdot 10^5$、只由 a-z 字符组成的字符串 $t$，计算 $t$ 的所有连续子串 $s$ 的 $B(s)$ 之和。

输入格式

输入由一个非空字符串组成，长度至多为 $3\cdot 10^5$，字符均为小写英文字母。

输出格式

输出一个整数，表示在输入字符串的所有子串中，总共最多能构成的 "bessie" 数量之和。

bessiebessie

14

abcdefghssijebessie

28

提示

有 12 个子串恰好包含 1 个 "bessie"，并且有 1 个字符串恰好包含 2 个 "bessie"，因此总计为 $12\cdot 1 + 1 \cdot 2 = 14$。

SCORING: Inputs 3-5: 字符串长度至多为 5000。 Inputs 6-12: 无额外限制。

题目来源：Brandon Wang 和 Benjamin Qi

标签: USACO|2023|Silver

来源

USACO|2023|Silver