自动搬运

查看原文

来自洛谷，原作者为

	chenxinyang2006 退役了，生涯回忆有空的时候再写

搬运于2025-08-24 22:18:38，当前版本为作者最后更新于2020-01-31 22:34:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 算法1

  枚举所有区间，然后扫一遍判断是否回文，暴力匹配求出包含 $s_2$ 的次数

  时间复杂度：$O(n ^ 4)$

• 算法2

  在算法1的基础上，把暴力匹配改成 $kmp$ 匹配；当然你也可以仿照算法3的做法，用暴力匹配

  时间复杂度：$O(n ^ 3)$

• 算法3

  在算法2的基础上，进行优化

  每次枚举一个左端点 $l$ ，然后从左往右扫一遍 $r$ ，边扫边匹配，每次 $O(1)$ 在 $(l,r - 1)$ 的基础上计算出 $(l,r)$ 中 $str2$ 出现的次数

  然后就是判定回文，可以用manacher，也可以每次枚举对称点，往两边暴力找。总之就是找出每个有效的回文区间，然后加上 $s_2$ 的出现次数就行

  时间复杂度：$O(n ^ 2)$

• 算法4

  枚举所有区间的做法肯定是不行了，得从点的角度来考虑问题

  可以先跑一遍 $kmp$ ，知道哪些点可以作为 $s_2$ 的左端点，将这些点标为 $1$ ，其他点标为 $0$ ，用 $a_i$ 表示这个值。然后问题就简化为：

  查询所有回文区间的区间和

  但是这样还是太过复杂，因为区间数量是 $n ^ 2$ 的，所以考虑从 $manacher$ 的角度解决问题

  $manacher$ 可以帮助我们求出每个对称点的最长回文串，这$n$个最长回文串实际上包含了所有最多$n ^ 2$个回文串

  实际上，想到这一步的话，问题已经迎刃而解了

  设这个最长回文串包含 $(l,r)$ ，那么其实就是求：

  $(a_l + ... a_r) + (a_{l + 1} + ... a_{r - 1}) + (a_{l + 2} + ... + a_{r - 2}) + ...$

  （最长回文串的答案） + （次长回文串的答案） + ……

  当然，这个式子是假的，因为你得考虑左端点在范围内，右边却超了的情况

  不过这不重要，总之，这个式子是可以快速计算的，它相当于给每个 $a_i$ 标了一个权值，然后求一个和

  那么这个实际上是两段等差数列加起来

  这个有一个通用套路就是前缀和

  设现在求和的段是$[l,r]$，如果公差为1，就是要求：

  $\quad \sum\limits_{i = l} ^ r a_i \times (i - l + 1)$

  $=\sum\limits_{i=l} ^ r (a_i \times i) - (\sum\limits_{i = l} ^ r a_i) \times l + \sum\limits_{i = l} ^ r a_i$

  显然，维护 $a_i \times i$ 的前缀和、 $a_i$ 的前缀和就可以算了

  另一端也是一样的，就不推了

  时间复杂度：$O(n)$

  Subtask 4是随便放的，想看看有没有 $O(n\ log\ n)$的奇怪解法

code