P8631 [蓝桥杯 2015 国 AC] 切开字符串 题解
zyc_lIIll
·
·
题解
P8631 [蓝桥杯 2015 国 AC] 切开字符串 题解
前言
看到这题没有人写题解，就打算写一篇。这也是蒟蒻的第一篇题解。
前置知识
manacher，SA。如果不会可以转至 manacher模板，SA模板，以及 我的博客。
题意概述
给一个长度为 n 的字符串 s，记 A_i 表示 s_{1\ldots i} 中本质不同的长度为奇数的回文串个数，B_i 表示 s_{i\ldots n} 中本质不同的长度不为奇数或不是回文串的子串个数，求 \max_{i=1}^{n-1}A_i\times B_{i+1}。
### 符号规定
$\operatorname{suf}(i)$ 表示从 $i$ 开始的后缀。$\operatorname{lcp}(i,j)$ 表示 $\operatorname{suf}(i),\operatorname{suf}(j)$ 的最长公共前缀。
$sa_i,rk_i,ht_i$ 分别代表排名为 $i$ 的后缀的开始位置、$\operatorname{suf}(i)$ 的排名、$\operatorname{lcp}(sa_i,sa_i-1)$。
$d_i$ 为以 $i$ 为中心的最长回文串半径。
### 题目分析
对于 $n\le 1000$ 我们可以暴力的 Hash 预处理出所有 $A_i$ 和 $B_i$，然后求答案即可。
那么对于 $n\le 10^5$ 来说其实也可以这样做，先预处理出 $A_i,B_i$，然后再统计答案。其实可以发现我们要求的可以分为三个部分：
1. 每个 $s$ 的后缀的本质不同子串数
2. 每个 $s$ 的前缀本质不同的长度为奇数的回文串数
3. 每个 $s$ 的后缀本质不同的长度为奇数的回文串数
首先我们来看第一个问题。因为要求本质不同子串数，所以很自然的想到 SA 来求解，可以参考 [P4070 [SDOI2016]生成魔咒](https://www.luogu.com.cn/problem/P4070) （~~其实是一模一样的题目~~），下面我讲一下具体如何做。
我们考虑一下 SA 求整个字符串本质不同子串数的原理：$ans=\sum_{i=1}^{n}(n-sa_i+1-ht_i)$，其实就是把所有子串先加上，再把所有重复的子串减去，那么我们求每个后缀的本质不同子串数也可以如此（记 $sum_i$ 表示 $s_{i\ldots n}$ 的本质不同子串数）：
我们倒序枚举 $s$ 的每一个字符，并维护一个 `set`，里面储存所有已经枚举过的字符 $s_i$ 的对应的后缀 $\operatorname{suf}(i)$ 的排名 $rk_i$，然后当我们枚举到 $s_j$ 时，找到 $rk_j$ 的前驱 $pre$，后继 $nxt$，则：
$$
sum_j=sum_{j+1}+(n-j+1)-\max(\operatorname{lcp}(sa_{pre},j),\operatorname{lcp}(j,sa_{nxt}))
$$
原理如下：
首先我们加入了 $s_j$，那么如果不考虑重复的子串，它会贡献 $n-j+1$ 个子串，但是由于它有重复的，所以说我们要把重复的减掉，而重复的子串其实也就是 $\operatorname{suf}(j)$ 和所有已经插入过的 $\operatorname{suf}(i)$ 的 $\operatorname{lcp}$ 的最大值，即 $\max_{i=j+1}^{n}\operatorname{lcp}(i,j)$，而根据 $height$ 数组的性质可以知道，这个最大值只有可能出现在 $\operatorname{lcp}(j,sa_{pre})$，$\operatorname{lcp}(j,sa_{nxt})$ 中，所以这样做是很正确的，下面给出这一部分的代码：
```cpp
set<int> S;
set<int> :: iterator it;
//下面用到的函数
void work(int x) {
int lst, nxt; mx = 0;
it = S.lower_bound(x);
nxt = (*it); lst = (*(--it));
if (lst >= 1 && lst <= n) mx = max(mx, lcp(lst, x));
if (nxt >= 1 && nxt <= n) mx = max(mx, lcp(x, nxt));
S.insert(x);
}
//主函数部分，倒序插入字符
S.clear(); S.insert(0); S.insert(n + 1); //插入 0 和 n+1 是为了防 RE
for (i = n; i >= 1; --i) {
work(rk[i]);
sum[i] = sum[i + 1] + 1ll * (n - i + 1 - mx);
S.insert(rk[i]);
}
```
第一个子问题解决了，接下来考虑剩下两个子问题。
其实这两个问题是一模一样的，下面我们只讨论第三个子问题，第二个子问题只需要把字符串翻转一下再按照第三个子问题的方法再做一遍即可。
因为是找本质不同的长度为奇数的回文串的个数，可以尝试结合 manacher 和 SA，思路可以参考一下 [P3649 [APIO2014] 回文串](https://www.luogu.com.cn/problem/P3649)。
比较暴力的想法是先用 manacher 将所有的回文串都找出来，然后按照左端点从大到小依次枚举，按照第一个子问题的方法一模一样的做即可，复杂度 $O(n^2\log n)$。
但其实可以优化的，考虑 manacher 是如何做到 $O(n)$ 的：**$r$ 端点只变化了 $n$ 次**。那么其实可以换句话说：
> **一个字符串的本质不同回文串的个数最多只有 $O(n)$ 级别**
所以说我们只考虑暴力增加 $d_i$ 时额外增多的回文串即可（因为只有这些回文串才**有可能**成为一个新的本质不同回文串），所以在做 manacher 的时候把得到的新的回文串的长度记录在改回文串的左端点处（每个位置开一个 `vector`），然后按照第一部分方法，找到 $len=\max(\operatorname{lcp}(i,j))$，然后在 `vector` 中 `lower_bound` 一下找到长度大于 $len$，即哪些回文串未出现过即可，代码如下：
```cpp
//用 manacher 加入回文串部分
for (i = n, l = n + 1; i >= 1; --i) {
if (i >= l) d[i] = min(d[mid * 2 - i], i - l + 1);
while (i + d[i] <= n && i - d[i] >= 1 && s[i + d[i]] == s[i - d[i]]) {
v[i - d[i]].push_back(2 * d[i] + 1);
d[i]++;
}
if (i - d[i] + 1 < l) {
l = i - d[i] + 1;
mid = i;
}
}
for (i = 1; i <= n; ++i) sort(v[i].begin(), v[i].end());
//统计处
S.clear(); S.insert(0); S.insert(n + 1);
memset(val, 0, sizeof(val));
for (i = n; i >= 1; --i) {
work(rk[i]); val[i] = val[i + 1]; //与上文中的 work 函数相同
if(v[i].back() <= mx) continue;
pos = upper_bound(v[i].begin(), v[i].end(), mx) - v[i].begin();
val[i] += 1ll * (v[i].size() - pos); //val[i]表示s[i~n]本质不同长度奇数回文串数
}
```
到这里已经可以做了，但其实还可以优化一下，因为有一个更加优美的结论：
> 如果将回文串记录在倒序枚举时它最早出现的位置的左端点上，那么每个字符 $s_i$ 处**最多只会储存一个回文串**
证明如下：
如果位置 $i$ 存了两个不同的回文串，长度分别为 $p,q$ 且 $p>q$，那么说明在 $s_{L\ldots R}$ 处（其中 $L=2\times (i+\lfloor \dfrac{q}{2}\rfloor) - (i+p-1)$，$R=2\times (i+\lfloor \dfrac{q}{2}\rfloor) - i$）是一个与 $s_{i\ldots i+p-1}$ 完全相同的字符串，与前提 **最早出现的位置** 冲突，故结论成立。
所以说就不同开 `vector` 了，只用在每个位置对回文串长度取 $\max$ 即可，即改成这样：
```cpp
//插入回文串
for(i = n, l = n + 1; i >= 1; --i) {
if(i >= l) d[i] = min(d[mid * 2 - i], i - l + 1);
while(i + d[i] <= n && i - d[i] >= 1 && s[i + d[i]] == s[i - d[i]]) {
v[i - d[i]] = max(v[i - d[i]], 2 * d[i] + 1);
d[i]++;
}
if(i - d[i] + 1 < l) {
l = i - d[i] + 1;
mid = i;
}
}
//统计处
S.clear(); S.insert(0); S.insert(n + 1);
for(i = n; i >= 1; --i) {
work(rk[i]);
val[i] = val[i + 1] + (mx < v[i]);
}
```
于是本题就完美的结束了，下面给出 **[完整代码](https://www.luogu.com.cn/paste/4c9l1dps)**。
### 后记
~~其实本蒟蒻觉得这题难度不止蓝~~，或许有更简单的方法吧。本题中给出的题目链接在 **[我的博客](https://www.cnblogs.com/zyc070419-blog/p/17151929.html)** 中都是有讲解的（~~虽然讲的有一点简略~~），但题目类型、套路挺多的（确信，如果本篇博客有哪里写的不对的地方也希望大家指出，我会及时更改。
本篇题解到这里就彻底结束了！