回文匹配 解析
chenxinyang2006 · · 题解
-
算法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 的角度解决问题实际上，想到这一步的话，问题已经迎刃而解了 设这个最长回文串包含 $(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