字符串（二）Manacher

· · 算法·理论

前言

::::info[AI 使用说明] 本文仅使用 deepseek 进行润色，保证人类贡献远大于 AI 贡献。 :::: ::::info[作者的神秘习惯] 本文算法描述中，除特别说明外，数组或字符串的下标都从 1 开始；代码实现中可能根据习惯使用从 0 开始的下标，已在相应位置标注。 :::: 上一篇好像有许多东西都被 deepseek 指出有小错误或者很模糊，本区被吓的给大佬们磕头了。\ 那么本篇应该质量会更低。\ 本来是想和一些别的串串知识点一起复习的，太懒了所以只复习了 Manacher。

Manacher

我们定义一个字符串 s 为回文串仅当 s 满足对于所有位置的 i 都满足 s_i=s_{|s|-i+1}。当然更好的说法是一个字符串是回文串，当且仅当它等于它反转后的字符串。

Problem:\ 求在一个满足 |s|\le 10^6 的字符串 s，求出它的最长回文子串长度。

我们考虑中心扩展法。即，我们对于所有的 |s| 的位置作为回文中心向两边扩展。但是，由于回文串有奇偶两种，于是我们考虑以 i 为中心，以 i,i+1 为中心分别扩展。 ::::info[例子]{open} 对于字符串 baddaba，我们从每一个位置出发能够扩展到的回文串是：

所以最长的回文子串应该是 baddab。从这里我们可以知道，从一个位置出发，奇数至少能扩展出来一个长度为 1 的回文子串（自己），而偶数可以是没有。
它正确的原因是，一个回文字符串，分别删除开头和结尾的字符依然是回文字符串（因为删去后剩下的字符串依然满足条件）。但是这样的时间复杂度是 $O(
我们首先考虑统一奇偶字符串，方式就是每两个字符之间都加上分隔符，比较常见的是#。这样所有回文都变成了奇数长度。但是它不会改变原本一个子串是回文串，因为如果是奇数长度的字符串那么对称位置的 # 会互相抵消。而偶数长度，就会变成以 # 为对称中心的串，于是同理了。\
那么新的串的长度就会变成 2\times n+1。设修改后的字符串为 t，我们设 p_i 为以 t_i 为中心的最长回文半径（包括中心），那么以 i 为中心的回文串长度就是 2\times p_i-1，对应到原串长度就是 p_i-1。\
我们考虑维护两个变量
- \text{id} 表示当前能延伸到最右边的回文串的中心位置。
- \text{mx} 这个回文串能到达的最右边界，我们定义它是第一个不包含的右端点。

对于当前位置 i，我们考虑：

::::info[初始化对吗]{open} 假设当前有一个以 \text{id} 为中心，右边界为 \text{mx} 的大回文串，对于它内部的任意位置 i，它的对称点 j 也在回文串内部。以 j 为中心的回文，在以 i 为中心的地方会有一个完全对称的回文。（因为 i 与 j 以 \text{id} 对称，那么以 j 为对称中心的一个字符串以 i 为中心也是对称串）但是这样 p_i=p_j 可能是有问题，就是它的镜像过来的回文子串不能超过右边界。所以初始为 \min \{p_j,\text{mx}-i\}。 :::: 随后我们向两边扩展（暴力）即可。具体的，只要 i-p_i\ge 1 并且 i+p_i\le |t|=2\times n+1 满足 t_{i-p_i}=t_{i+p_i} 就继续扩展。\ 这个东西的时间复杂度看起来也不是很好呢。但是注意到 \text{mx} 是单调不减的，每次成功扩展都会把 \text{mx} 往右推，所以总扩展次数是 O(n) 的。当然你也可以考虑分讨奇数偶数两种情况，不需要插分隔符。时间复杂度是同样的，思路是基本类似的。\ 例题：Manacher 板子 ::::success[插分隔符]

#include<bits/stdc++.h>
using namespace std;

const int N = 2e7 + 2e6 + 5;
int n,m;
string s,t;
int p[N];
int main() {
    cin >> s;
    n = s.size();
    t = "^#";
    for(int i = 0;i < n;i ++) {
        t += s[i];
        t += '#';
    }
    t += '$';
    m = t.size() - 1;
    int id = 0,mx = 0;
    int ans = 0;
    for(int i = 1;i <= m;i ++) {
        if(i < mx) p[i] = min(p[2 * id - i],mx - i);
        else p[i] = 1;
        while(t[i - p[i]] == t[i + p[i]]) p[i] ++;
        if(i + p[i] > mx) {
            id = i;
            mx = i + p[i];
        }
        ans = max(ans,p[i] - 1);
    }
    printf("%d",ans);
    return 0;
}

:::: ::::success[分讨奇偶]

#include<bits/stdc++.h>
using namespace std;

const int N = 1e7 + 1e6 + 5;
int n;
string s;
int d1[N],d2[N];
int main() {
    cin >> s;
    n = s.size();
    s = " " + s;
    for(int i = 1,l = 1,r = 0;i <= n;i ++) {
        int k;
        if(i > r) k = 1;
        else k = min(d1[l + r - i],r - i + 1);

        while(k <= i - 1 && i + k <= n && s[i - k] == s[i + k]) k ++;
        d1[i] = k;
        k --;
        if(i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
    for(int i = 1,l = 1,r = 0;i <= n;i ++) {
        int k;
        if(i > r) k = 0;
        else k = min(d2[l + r - i + 1],r - i + 1);

        while(k <= i - 2 && i + k <= n && s[i - k - 1] == s[i + k]) k ++;
        d2[i] = k;
        k --;
        if(i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i ++) {
        ans = max(ans,max(d1[i] * 2 - 1,d2[i] * 2));
    }
    printf("%d",ans);
    return 0;
}

::::

例一：拉拉队排练

题意：\ 求所有的奇数长度的回文子串按照长度降序排序后，前 k 的长度乘积（取模 19930726），如果总数小于 k 输出 -1。

由于插分割符的目的是统一奇偶，而本题只需要考虑奇数所以插不插分割符其实无所谓。那么我们直接跑 Manacher 得到 d_i 数组，表示所有的以 i 为中心的奇数回文半径。\ 以 i 为中心的奇数回文长度是 1,3,\dots 2\times d_i-1 一共有 d_i 个。如果全都跑出来时间和空间都会炸，所以我们用差分统计每个奇数长度的出现次数，然后对奇数下标前缀和即可。\ 然后我们从大到小取前 k 个，相同长度的快速幂即可。\ Tips:本题目只需要考虑奇数长度，那么差分的时候可以跳过偶数。 ::::success[P1659]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 5;
const int Mod = 19930726;
int n,k;
string s;
int d1[N];
int cnt[N];

int ksm(int a,int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

void Manacher() {
    for(int i = 1,l = 1,r = 0;i <= n;i ++) {
        int x;
        if(i > r) x = 1;
        else x = min(d1[l + r - i],r - i + 1);
        while(x <= i - 1 && i + x <= n && s[i - x] == s[i + x]) x ++;
        d1[i] = x;
        x --;
        if(i + x > r) {
            l = i - x;
            r = i + x;
        }
    }
}

signed main() {
    cin >> n >> k;
    cin >> s;
    s = " " + s;
    Manacher();
    for(int i = 1;i <= n;i ++) {
        cnt[1] ++;
        if(2 * d1[i] + 1 <= n) cnt[2 * d1[i] + 1] --;
    }
    for(int i = 3;i <= n;i += 2) cnt[i] += cnt[i - 2];
    int ans = 1;
    int tot = 0;
    for(int i = n;i >= 1;i --) {
        if(i % 2 == 0) continue;
        if(cnt[i] == 0) continue;
        int take = min(cnt[i],k - tot);
        ans = ans * ksm(i,take) % Mod;
        tot += take;
        if(tot >= k) break;
    }
    if(tot < k) puts("-1");
    else printf("%lld\n",ans);
    return 0;
}

::::

例题二：[POI 2010] ANT-Antisymmetry

题意：\ 我们定义反对称为，0,1 取反之后再将整个串反过来和原串一样的字符串。\ 给定一个 01 字符串，求有多少个子串是反对称的。

Tips:本题为作者很久以前做的题目，字符串下标从 0 开始。\ 注意到反对称指的是关于中心对称的两个字符不同。那么我们可以将 Manacher 的扩展条件换成

S_{i-k}\ne S_{i+k}

这样我们就可以得到所有位置 i 的反对称。\ 我们注意到，反对称串的对称中心一定是 (i,i+1)，如果只有一个数的话会无法匹配。所以反对称串一定是偶数。（所以如果不加分割符的话实际上扩展条件是 S_{i-k - 1}\ne S_{i+k}。）\ 这样我们跑出来的 d_i 就是以 i 为右中心的最长反对称半径。那么实际上以 i 为有中心的反对称子串有 d_i 个，所以答案就是 \sum_{i=0}^{n-1}d_i。 ::::success[P3501]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 5;
int n,d[N],ans = 0;
string S; 
inline void manacher(){
    for(int i = 0,l = 0,r = -1;i < n;i ++) {
        int k;
        if(i > r) k = 0;
        else k = min(d[l + r - i + 1],r - i + 1);
        while(k <= i - 1 && k + i < n && S[i - k - 1] != S[i + k]) k ++;
        d[i] = k;
        k --;
        if(i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }
}
signed main(){
    scanf("%lld",&n);
    cin >> S;
    manacher();
    for(int i = 0;i < n;i ++) {
        ans += d[i];
    }
    printf("%lld\n",ans);
    return 0;
}

::::

例题三：最长双回文串

题意：\ 求最长的能够分成两个非空回文串的字符串。

我们分别预处理出来以 i 为左端点的最长回文长度和以 i 为右端点的最长回文长度，分别记作 L_i 和 R_i。只有左右端点恰好是 i 的回文才能直接贡献给 L_i,R_i，所以我们 Manacher 求出每一个回文区间 [l,r] 后，直接更新 L_l 和 R_r 即可。\ 如果 [l,r] 是回文串，那么去掉两端之后 [l+1,r-1] 仍然是回文串，所以如果以 i-1 为左端点的最长回文长度 L_{i-1}，那么以 i 为左端点的回文串至少长度为 L_{i-1}-2，右端点同理。

L_i=\max\{L_i,L_{i-1}-2\}\\ R_i=\max\{R_i,R_{i+1}-2\}

那么我们枚举所有的分界点 i，左半边是 R_i，右半边是 L_{i+1}，答案是

\max_{1\le i<n}R_i+L_{i+1}

::::success[P4555]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int n;
string s;
int d1[N],d2[N];
int L[N],R[N];

void Manacher() {
    for(int i = 1,l = 1,r = 0;i <= n;i ++) {
        int k;
        if(i > r) k = 1;
        else k = min(d1[l + r - i],r - i + 1);
        while(k <= i - 1 && i + k <= n && s[i - k] == s[i + k]) k ++;
        d1[i] = k;
        k --;
        if(i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
    for(int i = 1,l = 1,r = 0;i <= n;i ++) {
        int k;
        if(i > r) k = 0;
        else k = min(d2[l + r - i + 1],r - i + 1);
        while(k <= i - 2 && i + k <= n && s[i - k - 1] == s[i + k]) k ++;
        d2[i] = k;
        k --;
        if(i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }
}

signed main() {
    cin >> s;
    n = s.size();
    s = " " + s;
    Manacher();
    for(int i = 1;i <= n;i ++) {
        int len = 2 * d1[i] - 1;
        int l = i - d1[i] + 1,r = i + d1[i] - 1;
        L[l] = max(L[l],len);
        R[r] = max(R[r],len);
    }
    for(int i = 1;i <= n;i ++) {
        if(d2[i] > 0) {
            int len = 2 * d2[i];
            int l = i - d2[i],r = i + d2[i] - 1;
            L[l] = max(L[l],len);
            R[r] = max(R[r],len);
        }
    }
    for(int i = 2;i <= n;i ++) L[i] = max(L[i],L[i - 1] - 2);
    for(int i = n - 1;i >= 1;i --) R[i] = max(R[i],R[i + 1] - 2);
    int ans = 0;
    for(int i = 1;i < n;i ++) {
        if(R[i] > 0 && L[i + 1] > 0)ans = max(ans,R[i] + L[i + 1]);
    }
    printf("%lld\n",ans);
    return 0;
}

::::

例题四：回文匹配

给定两个字符串 s（长度为 n）和 t（长度为 m），对于 s 的每一个长度为奇数的回文子串，统计 t 在该回文子串中出现的次数，并求和。

首先我们解决 s 的所有长度为奇数的回文子串。那么我们直接不插入分隔符跑 Manacher 找到回文半径 d_i，那么一共需要判断 \sum_{i=1}^n d_i 个子串跑 KMP。因为统计 t 在某一个字符串内的所有的初始位置是板子。\ 我们对于任意的区间 [l,r]，设 t 在其中出现的次数为：（设 \text{match}_x 表示 t 从 s_x 开始出现一个完整的子串）

\text{count}(l,r)=\sum_{x=l}^{r-m+1}\text{match}_x

那么我们使用前缀和优化即可 O(1) 得到 \text{count}(l,r)。下文设 sum_i 为 \text{match} 的前缀和。\ 如果直接枚举显然会超时，因为一个回文中心会产生多个回文子串。对于固定的中心 i,半径 k 的回文范围。对于固定中心 i 我们需要

F(i)=\sum_{k=1}^{d_i}\text{sum}_{i+k-1-m+1}-\text{sum}_{i-k+1-1}

那么我们对这一坨式子进行简化：

F(i)=\sum_{k=1}^{d_i}\text{sum}_{i+k-m}-\text{sum}_{i-k}

我们设 r=i+k-1，那么 k=r-i+1。那么实际上，k 从 1\sim d_i，r 从 i\sim i+d_i-1。那么我们的式子就会转化为

F(i)=\sum_{k=1}^{d_i}\text{sum}_{r-m+1}-\text{sum}_{i-(r+1-i)}

进一步，我们化简之后还可以拆成两个部分：

F(i)=\sum_{r=i}^{i+d_i-1}\text{sum}_{r-m+1}-\sum_{r=i}^{i+d_i-1}\text{sum}_{2\times i-r-1}

那么两个式子都再使用一遍前缀和优化即可。\ 注意只需要对 d_i\ge \frac{m+2}{2} 的数求和。因为剩下的长度不足以容纳一个完整的 t，直接算会出错。\ 另外本题答案可能很大，代码里 ans 用的是 unsigned int，理论上存在溢出风险，实际实现时建议使用 unsigned long long 或 __int128。 ::::success[P6216]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 4e6 + 5;
int n,m;
string s,t;
int nxt[N],p[N];
int match[N],sum[N],pre[N];

void gnext() {
    nxt[1] = 0;
    int j = 0;
    for(int i = 2;i <= m;i ++) {
        while(j && t[j + 1] != t[i]) j = nxt[j];
        if(t[j + 1] == t[i]) j ++;
        nxt[i] = j;
    }
}

void kmp() {
    int j = 0;
    for(int i = 1;i <= n;i ++) {
        while(j && t[j + 1] != s[i]) j = nxt[j];
        if(t[j + 1] == s[i]) j ++;
        if(j == m) {
            match[i - m + 1] = 1;
            j = nxt[j];
        }
    }
}

void manacher() {
    for(int i = 1,l = 1,r = 0;i <= n;i ++) {
        int x;
        if(i > r) x = 1;
        else x = min(p[l + r - i],r - i + 1);
        while(x <= i - 1 && i + x <= n && s[i - x] == s[i + x]) x ++;
        p[i] = x;
        x --;
        if(i + x > r) {
            l = i - x;
            r = i + x;
        }
    }
}

int gp(int idx) {
    if(idx < 0) return 0;
    if(idx > n) return pre[n];
    return pre[idx];
}

signed main() {
    cin >> n >> m;
    cin >> s >> t;
    s = " " + s;
    t = " " + t;
    s += '$';
    t += '$';

    gnext();
    kmp();
    manacher();

    for(int i = 1;i <= n;i ++) sum[i] = sum[i - 1] + match[i];
    for(int i = 1;i <= n;i ++) pre[i] = pre[i - 1] + sum[i];

    int kt = (m + 2) / 2;
    unsigned int ans = 0;
    for(int i = 1;i <= n;i ++) {
        if(p[i] < kt) continue;
        ans += gp(i + p[i] - m) - gp(i + kt - m - 1) - (gp(i - kt) - gp(i - p[i] - 1));
    }

    printf("%u\n", ans);
    return 0;
}

::::

例题五：绿绿和串串

题意：\ 给定字符串 S，判断它的哪些前缀可以通过不断以末尾字符以轴进行翻转最后覆盖整个 S。

它的过程实质上就是以结尾字符为对称中心，把左边的字符复制到右边。容易注意到一次翻转能覆盖到多远，取决于以 i 为中心的回文能延伸到多远。\ 设以 i 为中心的回文，右端点最远能到 r（在原串中的位置）。\ 我们不妨看一下，由于一个长度为 m 的字符串 T 翻转之后的字符串是：

T_{1,2,\dots,m,m-1,\dots,1}

设 T 为 S 的一个子串，以 m 为中心的回文串的右端点最多能到为 r。那么一次翻转后，新字符串的前 r 个字符恰好是 S_{1,2,\dots,r}。\ 那么我们分别讨论：

::::info[P5446]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 5;
int n,T;
string s;
int d1[N];
bool ok[N];

void Manacher() {
    for(int i = 1,l = 1,r = 0;i <= n;i ++) {
        int k;
        if(i > r) k = 1;
        else k = min(d1[l + r - i],r - i + 1);
        while(k <= i - 1 && i + k <= n && s[i - k] == s[i + k]) k ++;
        d1[i] = k;
        k --;
        if(i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
}

signed main() {
    scanf("%d",&T);
    while(T --) {
        cin >> s;
        n = s.size();
        s = " " + s;
        Manacher();
        for(int i = 1;i <= n;i ++) ok[i] = false;
        for(int i = n;i >= 1;i --) {
            int r = i + d1[i] - 1;
            int l = i - d1[i] + 1;
            if(r >= n) ok[i] = true;
            else if(l == 1 && ok[r]) ok[i] = true;
        }
        for(int i = 1;i <= n;i ++) {
            if(ok[i]) printf("%lld ",i);
        }
        puts(""); 
    }
    return 0;
}

::::

例题六：泪雨 Namid[A]me

题意：\ 给定一个只含小写字母和 ? 的长度 n 的字符串 S。定义一个子串是泪雨，当且仅当：

  • 它是回文串；
  • 其中 ? 的数量不少于字母的数量。 要求对于所有是泪雨的子串，求出它们中 ? 的位置下标之和，再对所有泪雨子串的这个和求和。位置下标从 1 开始。

直接对于所有的回文串暴力判断是 O(n^3) 的。对于一个中心进行扩展的时候计算可以快到 O(n^2)。那么我们考虑对每个回文中心，一次性算出它产生的所有泪雨的贡献。\ 设 ? 数量为 q，一个回文字符串长度为 \text{len}，字母数量就是 \text{len}-q。显然由题得到

2\times q\ge \text{len}

设回文区间为 [l,r]，那么我们设一个数组 a，a_i=1 仅当 S_i=?，否则 a_i=-1。那么我们可以得到：

q-(\text{len}-q)=q+(-(\text{len}-q))=\sum_{i=l}^ra_i\ge 0

由于我们要求下标和，设固定中心和半径分别为 i,k，所以实际上我们需要求

\sum_{j=i-k+1}^{i+k-1}j\times [S_j=?]

那么就是对所有区间和 \ge 0 的 k 累加位置和。考虑从 Manacher 的时候就进行更新，具体的，区间和加上 a_{i-k}+a_{i+k}，位置和就是 S_{i-k}=? 的时候加上 i-k，S_{i+k}=? 的时候加上 i+k 即可。\ 下文我们默认 Manacher 是插分隔符的，且本题代码里原字符在奇数位、分隔符在偶数位，开头不插分隔符。\ 我们考虑维护 ? 的数量，那么对于中心 i，如果当前回文中有 \text{cnt} 个 ?，他们在原来的串的位置和是

\text{cnt}\times \frac{i+1}{2}

因为对称的两个 (i-k,i+k) 他们的原串位置和是：

\frac{i-k+1}{2}+\frac{i+k+1}{2}=i+1

我们设 \text{tot}_i 表示当前中心下，所有满足泪雨条件的半径的 \text{cnt} 之和。最后该中心对答案的贡献是：

\text{tot}_i\times \frac{i+1}{2}

::::success[P12977]

#include<bits/stdc++.h>
using namespace std;

const int N = 2e7 + 5;
int n,m,d[N],len[N];
char s[N];
__int128 cnt[N],sum[N];
__int128 ans;

__int128 Manacher() {
    __int128 res = 0;
    for(int i = 1,r = 0,mid = 0;i <= m;i ++) {
        if(r >= i) {
            int p = mid * 2 - i;
            d[i] = d[p];
            cnt[i] = cnt[p];
            sum[i] = sum[p];
            len[i] = len[p];
            while(d[i] > r - i) {
                int R = p + d[i];
                if(2 * cnt[i] >= len[i] && s[R] != '|') sum[i] -= cnt[i];
                if(s[R] == '?') cnt[i] -= 2;
                if(s[R] != '|') len[i] -= 2;
                d[i] --;
            }
        } else {
            len[i] = (s[i] == '|') ? 0 : 1;
            cnt[i] = sum[i] = 0;
            if(s[i] == '?') {
                cnt[i] = 1;
                if(2 * cnt[i] >= len[i]) sum[i] = 1;
            }
        }

        while(s[i - d[i] - 1] == s[i + d[i] + 1]) {
            d[i] ++;
            if(s[i + d[i]] != '|') {
                len[i] += 2;
                if(s[i + d[i]] == '?') cnt[i] += 2;
            }
            if(2 * cnt[i] >= len[i] && s[i + d[i]] != '|') sum[i] += cnt[i];
        }

        res += (__int128)sum[i] * (__int128)(i + (__int128)1) / (__int128)2;
        if(i + d[i] >= r) {
            r = i + d[i];
            mid = i;
        }
    }
    return res;
}

void print(__int128 x) {
    if(x == 0) { putchar('0'); return; }
    if(x < 0) { putchar('-'); x = -x; }
    char buf[50]; int len = 0;
    while(x) { buf[len++] = x % 10 + '0'; x /= 10; }
    while(len) putchar(buf[--len]);
}

signed main() {
    scanf("%d",&n);
    s[0] = '~';
    for(int i = 1;i <= n;i ++) {
        cin >> s[i * 2 - 1];
        s[i * 2] = '|';
    }
    m = 2 * n;
    s[m + 1] = '$';
    ans = Manacher();
    print(ans);
    putchar('\n');
    return 0;
}

::::