Manacher
对于一个字符串 \(s\),如果 \(s=rev(s)\),则称 \(s\) 为回文串,称下标 \(\lfloor\frac{|s|}{2}\rfloor\) 为 \(s\) 的回文中心。
当 \(|s|\) 是偶数时,\(s\) 的回文中心和字符串中心不重合。为了避免这种情况,我们将原串中相邻两个字符之间都插入一个特殊字符 $
(%
,#
等)。
aabaabaa
\(\rightarrow\) $a$a$b$a$a$b$a$a$
这样,所有 \(|s|\) 为偶数的回文串就都变成了一个 \(|s|\) 为奇数的回文串,回文中心和字符串的正中心相重合。现在我们只需考虑长度为奇数的回文串。
对于字符串 \(s\),定义 \(z[i]\) 表示以下标 \(i\) 为回文中心,极长的回文子串的回文半径。Manacher(马拉车)算法可以在 \(O(n)\) 的时间内求出 \(z[i]\)。其线性的时间复杂度依赖于 \(\max_{j\le i}\{j+z[j]\}\) 的增量为 \(O(n)\) 级别。
考虑从左往右遍历字符串的每一个字符,设当前枚举到第 \(i\) 个字符,\(j+z[j]\) 在 \(j=k<i\) 处取到最大值。考虑 \(i\) 关于 \(k\) 对称的位置 \(p=2k-i\),Manacher 的核心思想就是从 \(p\) 转移到 \(i\)。
分类讨论
\(\large case\ 1\)
\[
i> k+z[k]
\]
此时不能从 \(p\) 转移到 \(i\)。但是直接暴力扩展即可,这会增大 \(\max_{j\le i}\{j+z[j]\}\),均摊正确。
\(\large case\ 2\)
\[
p-z[p]<k-z[k]
\]
由于 \(s\big[k-z[k]-1\big]\ne s\big[k+z[k]+1\big]\),因此 \(z[i]=k+z[k]-i\);
\(\large case\ 3\)
\[
p-z[p]>k-z[k]
\]
\(k\) 的回文区域包含了 \(p\) 和 \(i\) 的回文区域,因此 \(z[i]=z[p]\);
\(\large case\ 4\)
\[
p-z[p]=k-z[k]
\]
由于式子中存在两个不等号,因此我们无法判断 \(z[i]\) 能否在 \(z[p]\) 的基础上继续扩展。然而此时 \(i+z[i]= k+z[k]\),直接暴力扩展将会增大 \(\max_{j\le i}\{j+z[j]\}\),均摊正确。
代码中,我们一般将 \(case\ 2,3,4\) 合并考虑:直接取出 \(z[p]\),然后 \(z[i]\leftarrow \min(z[p], k+z[k]-i)\),然后直接暴力扩展 \(z[i]\)。
求出 \(z\) 之后,我们分讨回文中心是否为 $
,即可区分奇回文串和偶回文串。通过简单的处理就可以得到 z0[i]
和 z1[i]
,分别表示回文中心为 \(i\) 的偶回文串和奇回文串的最长回文半径。
模板代码
| int z[2 * N], z0[N], z1[N];
void manacher() {
s1.clear();
s1.push_back('$');
for(int i = 0; i < n; i++) {
s1.push_back(s[i]);
s1.push_back('$');
}
nn = s1.size();
int k = 0;
for(int i = 1; i < nn; i++) {
if(i <= k + z[k]) z[i] = min(k + z[k] - i, z[2 * k - i]);
else z[i] = 0;
while(i + z[i] < nn && i - z[i] >= 0 && s1[i + z[i]] == s1[i - z[i]]) {++z[i]; } --z[i];
if(i + z[i] > k + z[k]) k = i;
}
// 为了方便后面的处理,z0 和 z1 的下标从 1 开始
for(int i = 0; i < nn; i += 2) z0[i / 2] = z[i] / 2; // i 是偏左的回文中心
for(int i = 1; i < nn; i += 2) z1[i / 2 + 1] = z[i] / 2; // 奇回文串的回文中心就是正中心
}
|
题意
称一个字符串是好的,当且仅当它是一个偶回文串或由若干偶回文串拼接而成。
给定一个长度为 \(n\) 的字符串 \(s\),求有多少 \(s\) 的子串是好的。
\(n\le 5\times 10^5\)
err-tag
题意
给定一个长为 \(n\) 的字符串,保证所有字符为小写字母。你可以将至多一个字母替换为任意小写字母,使得这样操作之后字符串中的回文子串数量最多。
输出字典序最小的方案,以及对应的回文子串数量。
\(n\le 3\times 10^5\)
考虑到 \(n\Sigma\) 很小,我们尝试求出每一种修改方案对回文子串数量的贡献。
我们尝试枚举回文串的回文中心 \(x\),然后考虑修改位置 \(i\) 对回文中心为 \(x\) 的回文串的影响。
- 如果 \(i\in \big[x-z[x],x+z[x]\big]-\{x\}\),那么将会减少 \(\min\big((x+z[x])-i,i-(x-z[x])\big)+1\) 个回文串。这里的贡献可以用区间加等差数列解决;
- 如果 \(i=x-z[x]-1\) 或 \(i=x+z[x]+1\),考虑 \(x-z[x]-2\) 前缀和 \(x+z[x]+2\) 后缀可以将回文串扩展多少;这一步可以使用后缀数组求出;
- 其余情况,\(i\) 的修改不会影响到 \(x\);
离线区间加等差数列是 \(O(1)\) 的;后缀数组是 \(O(n\log n)\) 的;因此时间复杂度为 \(O(n\Sigma+n\log n)\)。
代码
| #include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 3e5 + 10;
const int LOGN = 21;
int n, nn;
string s, s1;
int z0[N], z1[N];
void manacher() {
static int z[2 * N];
s1.clear();
s1.push_back('$');
for(int i = 0; i < n; i++) {
s1.push_back(s[i]);
s1.push_back('$');
}
nn = s1.size();
int k = 0;
for(int i = 1; i < nn; i++) {
if(i <= k + z[k]) z[i] = min(k + z[k] - i, z[2 * k - i]);
else z[i] = 0;
while(i + z[i] < nn && i - z[i] >= 0 && s1[i + z[i]] == s1[i - z[i]]) ++z[i]; --z[i];
if(i + z[i] > k + z[k]) k = i;
}
for(int i = 0; i < nn; i += 2) z0[i / 2] = z[i] / 2;
for(int i = 1; i < nn; i += 2) z1[i / 2 + 1] = z[i] / 2;
}
namespace SA {
int n, m;
int sa[2 * N], rk[2 * N], tp[2 * N], cnt[2 * N], ht[2 * N];
int mn[LOGN][2 * N];
int lg[2 * N];
void sort() {
for(int i = 1; i <= m; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) ++cnt[rk[i]];
for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for(int i = n; i >= 1; i--) {
sa[cnt[rk[tp[i]]]--] = tp[i];
}
}
void get_sa() {
m = 30;
for(int i = 1; i <= n; i++) rk[i] = s1[i] - 'a' + 1;
for(int i = 1; i <= n; i++) tp[i] = i;
sort();
for(int w = 1; w < n; w <<= 1) {
int p = 0;
for(int i = n - w + 1; i <= n; i++) tp[++p] = i;
for(int i = 1; i <= n; i++) {
if(sa[i] > w) tp[++p] = sa[i] - w;
}
sort();
for(int i = 1; i <= n; i++) tp[i] = rk[i];
rk[sa[1]] = 1;
for(int i = 2; i <= n; i++) {
if(tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) rk[sa[i]] = rk[sa[i - 1]];
else rk[sa[i]] = rk[sa[i - 1]] + 1;
}
m = rk[sa[n]];
if(m == n) break;
}
}
void get_height() {
int k = 0;
for(int i = 1; i <= n; i++) {
k -= (bool)k;
if(rk[i] == 1) continue;
int j = sa[rk[i] - 1];
while(i + k <= n && j + k <= n && s1[i + k] == s1[j + k]) ++k;
ht[rk[i]] = k;
}
}
void init_st() {
for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= n; i++) mn[0][i] = ht[i];
for(int k = 1; k < LOGN; k++) {
for(int i = 1; i + (1 << k) - 1 <= n; i++) {
mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << k - 1)]);
}
}
}
int query_st(int x, int y) {
x = rk[x], y = rk[y];
if(x > y) swap(x, y);
++x;
int d = lg[y - x + 1];
return min(mn[d][x], mn[d][y - (1 << d) + 1]);
}
void init() {
s1 = s;
reverse(s1.begin(), s1.end());
s1 = s + s1;
n = s1.size();
s1 = '#' + s1;
get_sa();
get_height();
init_st();
}
int query(int x, int y) {
if(x <= 0 || 2 * y > n) return 0;
return min(min(x, n / 2 - y + 1), query_st(n - x + 1, y));
}
}
ll d[26][N], d1[N], d2[N];
void add(int p, int len, int a, int b) {
d1[p] += a;
d1[p + len] -= a + len * b;
d2[p] += b;
d2[p + len] -= b;
}
int main() {
cin >> n >> s;
SA::init();
manacher();
for(int i = 1; i <= n; i++) {
if(z0[i]) {
add(i + 1, z0[i], -z0[i] - 1, 1);
add(i - z0[i] + 1, z0[i], 0, -1);
}
if(z1[i]) {
add(i + 1, z1[i], -z1[i] - 1, 1);
add(i - z1[i], z1[i], 0, -1);
}
}
for(int i = 1; i <= n; i++) d1[i] = d1[i] + (d2[i] += d2[i - 1]);
for(int i = 1; i <= n; i++) {
for(int k = 0; k < 26; k++) d[k][i] = d[k][i - 1] + d1[i];
}
ll ans = 0;
for(int i = 1; i <= n; i++) {
ans += z0[i] + z1[i] + 1;
}
s = '#' + s;
for(int i = 1; i <= n; i++) {
int j1 = i - z0[i];
int j2 = i + z0[i] + 1;
if(j1 <= 0 || j2 > n) continue;
int tmp = SA::query(j1 - 1, j2 + 1) + 1;
d[s[j2] - 'a'][j1] += tmp;
d[s[j1] - 'a'][j2] += tmp;
}
for(int i = 1; i <= n; i++) {
int j1 = i - z1[i] - 1;
int j2 = i + z1[i] + 1;
if(j1 <= 0 || j2 > n) continue;
int tmp = SA::query(j1 - 1, j2 + 1) + 1;
d[s[j2] - 'a'][j1] += tmp;
d[s[j1] - 'a'][j2] += tmp;
}
int ansk = 0, ansi = 0;
for(int i = 1; i <= n; i++) {
for(int k = 0; k < 26; k++) {
if(!ansi || d[k][i] > d[ansk][ansi] || (d[k][i] == d[ansk][ansi] && i != ansi && ansk > s[ansi] - 'a')) {
ansi = i;
ansk = k;
}
}
}
if(d[ansk][ansi] < 0) cout << ans << '\n' << s.substr(1, n) << endl;
else if(d[ansk][ansi] == 0 && ansk > s[ansi] - 'a') cout << ans << '\n' << s.substr(1, n) << endl;
else {
s[ansi] = ansk + 'a';
cout << ans + d[ansk][ansi] << '\n' << s.substr(1, n) << endl;
}
return 0;
}
|