题解：AT_nikkei2019_2_final_h 逆にする関数

· · 题解

先讲讲 Manacher 怎么做。

钦定以下指的回文串是长度为奇数的 广义的回文串 ，我们将原字符串中每两个字符之间插入一个字符，求回文串就是 广义的回文串。

定义广义的回文串为翻转之后与原串相等的字符串。

考虑对于每个中心 i 求出 f_i，表示 [i-j,i+j] 是回文串当且仅当 j<f_{i}。

一个很暴力的想法就是枚举 f_{i} 暴力匹配 s_{i-f_{i}} 和 s_{i+f_{i}}。

考虑优化。从小到大枚举 i，求 f_{i}。维护 \max_{j=1}^{i-1} j+f_{j}，也就是他前面右端点最靠右的区间（若 右端点一样 选 j 最大的）。

若 i\geq j+f_{j}，进行上述暴力。

若 i<j+f_{j}，考虑让 i 继承 f_{2j-i} 的信息，也就是在这个回文串里 i 对应的位置的信息。

若 i+f_{2j-i}>j+f_{j}，意味着超出了这个回文区间信息不能保真，所以我们取到最大 f_{i}=j+f_{j}-f_{2j-i}，然后再暴力。

复杂度证明：

设 r=j+f_{j}，每次执行一次上述“暴力”，r\gets r+1，所以时间复杂度 O(n)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1.1e7+10;
int n,f[N*2];
string s="##";
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen("gsw.in","r",stdin);
    // freopen("gsw.out","w",stdout);
    char c;
    while(cin>>c) s+=c,s+='#';
    int r=0,j=0; s='!'+s+'?';
    n=s.size();
    for(int i=1;i<=n;i++){
        f[i]=(r>i?min(f[j*2-i],r-i):1);
        while(s[i-f[i]]==s[i+f[i]]) f[i]++;
        if(i+f[i]>r) r=i+f[i],j=i;
    }
    int Max=0;
    for(int i=1;i<=n;i++) Max=max(Max,f[i]-1);
    cout<<Max<<'\n';
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}

然后就是这道题，发现与回文串形式很类似，区间 [l,r] 贡献 \ne 0 当且仅当反转之后与原串构成双射，称之为 好串。一个 好串 的贡献为 m^{m-颜色数量}。

考虑用类似 Manacher 思想去做，求出 f_{i}，表示 [i-j,i+j] 是 好串 当且仅当 j<f_{i}，可以顺便维护 [i-f_{i}+1,i+f_{i}-1] 的颜色数量和 \sum m^{m-颜色数量}。

与上面类似，维护右端点最靠右的 好串。

若 i\geq j+f_{j}，进行暴力。

若 i<j+f_{j}，考虑继承信息。

若 i+f_{2j-i}>j+f_{j}，考虑暴力回退 f_{2j-i} 使得没有超出。

复杂度证明：

对于一次回退的时间复杂度是 O(i+f_{2j-i}-j-f_{j})。

根据定义有 2j-i+f_{2j-i}\leq j+f_{j}。

移项有 i+f_{2j-i}-j-f_{j}\leq 2i-2j。

设 k=i-j，做完这次操作之后会将 k\gets 0，意味着我们已 O(k) 的时间复杂度将 k\gets 0，然而 k 的总增加量为 O(n)，所以总时间复杂度 O(n)。

讲的更好