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; // 奇回文串的回文中心就是正中心
}

CF1827C Palindrome Partition

题意

称一个字符串是好的，当且仅当它是一个偶回文串或由若干偶回文串拼接而成。

给定一个长度为 \(n\) 的字符串 \(s\)，求有多少 \(s\) 的子串是好的。

\(n\le 5\times 10^5\)

err-tag

CF1913F Palindromic Problem

题意

给定一个长为 \(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;
}