题目传送门

题意简述

给定一个仅由 E 和 P 构成的环形字符串 $B$（$B$ 的串尾和串首相连）。询问 $B$ 中有多少连续子串同时满足：

• 长度不大于 $S$；
• 串中含有至少一个 E。

解析

正解是非常好想的咕！

首先，看到“环形”之后，立刻要想到展开咕！下面的数组都要开两倍长度咕！

然后思路就很清晰了咕！就是依次统计以第 $i$（$1\le i\le |B|$）位开始的，长度不超过 $S$ 的所有字符串中，有多少含有 E 就好了咕！

这个问题很显然可以使用滑动窗口咕！

首先扫一遍 $B$，在 $pos$ 数组中按顺序记录下其中为 E 的所有位置咕！

然后对 $pos$ 数组中当前已有的所有元素 $+|B|$ 后的值也按顺序放进 $pos$ 数组里咕！

最后用滑动窗口扫一遍就好了咕！答案要开 long long 咕！

扫滑动窗口的具体步骤为：

• 先将所有 $1\le pos_i\lt S$ 的位置按顺序放入一个队列中。
• 按照 $i$ 从 $1$ 到 $|B|$ 的顺序，执行：
• • 判断 $i+S-1$ 的位置上是否为 E。若是，则放入队列尾部；
• • 判断队列是否非空且 $i-1$ 的位置是否还在队列中。若是，弹出队首（易证，如果 $i-1$ 在队中，则它一定在队首）；
• • 判断队列是否非空。若是，将答案加上 $($队首 $-i)$ 的值。（末尾在队首之前的子串一定一个 E 都没有，末尾在队首及之后的子串一定有队首位置上的 E）

如果不在第二步判断队列是否非空，下面这组数据会卡掉你的代码（同时，你会喜提 WA on test #18）：

PEP
1

答案显然为 $1$。

滑动窗口时间复杂度 $\mathcal{O}(|B|+S)$，完全不需要担心 TLE 的问题咕！

代码参见这个提交记录咕！不要抄袭咕！

谢谢阅读咕！