Codeforces-1913F：Palindromic Problem（后缀数组）

F. Palindromic Problem
time limit per test：5 seconds
memory limit per test：512 megabytes
input：standard input
output：standard output

You are given a string $s$ of length $n$, consisting of lowercase Latin letters.

You are allowed to replace at most one character in the string with an arbitrary lowercase Latin letter.

Print the lexicographically minimal string that can be obtained from the original string and contains the maximum number of palindromes as substrings. Note that if a palindrome appears more than once as a substring, it is counted the same number of times it appears.

The string $a$ is lexicographically smaller than the string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a\ne b$;
• in the first position where $a$ and $b$ are different, the string $a$ contains a letter that appears earlier in the alphabet than the corresponding letter in $b$.

Input
The first line contains one integer $n(1\le n\le 3?10^5)$ — the number of characters in the string.

The second line contains the string $s$ itself, consisting of exactly $n$ lowercase Latin letters.

Output
In the first line, print one integer — the maximum number of palindromic substrings that can be obtained using the operation described in the statement at most once.

In the second line, print the string that can be obtained from $s$ and has the maximum possible number of palindromic substrings. If there are multiple answers, print the lexicographically smallest one.

Examples
input
5
aabaa
output
15
aaaaa

input
5
aaaaa
output
15
aaaaa

input
4
awoo
output
7
aooo

思路：考虑遍历$S$，枚举求出替换每个字符后的最多回文串数量。记$L_x$为以$x$为中心的回文串半径，当我们枚举替换到第$k$个位置的字符时，回文串数量有以下2种情况会减少：

• 减少 $(x+L_x?k)$，其中 $x<i$ 且 $x+L_x>k$，即在回文串中心$x$在$k$前面，并且该回文串包含$k$，当替换$S_k$时，这个回文串长度会变短。
• 减少 $(k?(x?L_x))$，其中 $x>i$ 且 $x?L_x<k$，即在回文串中心$x$在$k$后面，并且该回文串包含$k$，当替换$S_k$时，这个回文串长度会变短。

回文串减少的数量，我们可以用manacher算法或者后缀数组预处理求出每个$L_i$，根据上面条件，利用前缀和求出替换每个$S_k$后，回文串会减少的数量$d_k$。
接下来只需要求出替换$S_k$后可能会增加的回文串数量，容易想到当且仅当$x+L_x=k(x<k)$或者$x?L_x=k(x>k)$时，即回文串$L_x$长度刚好在$k$处终止，此时替换$S_k$才可能会使$L_x$变长、回文串数量增加。

$L_x$增加的长度即增加的回文串数量，而增加的长度就是$S[x?L_x,...,0]$和$S[k,...,n](x<k)$的最长公共前缀$(LCP)$的长度，同理当$x>k$时，增加的长度为$LCP(S[k,...,0],S[x+L_x,...,n])$的长度。

求公共前缀，我们就可以将$S$翻转后与原串$S$拼接，然后利用后缀数组 ${\log }_{2}n$ 查询$LCP$的长度。
求出回文串的减少和增加数量后，直接更新答案即可。复杂度$O(26?n?{\log }_{2}n)$。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<ll,ll>
#define bit bitset<100000>
using namespace std;
const int MAX=3e5+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX/2;
const double PI=acos(-1.0);
typedef long long ll;
struct SA
{
    int n;
    vector<int>sa,rk,height,c;
    vector<vector<int>>nex;
    SA(const string &s)
    {
        n=sz(s);
        rk.resize(n);height.resize(n);
        sa.resize(n);nex.resize(n);

        int m=*max_element(s.begin(),s.end());
        c.assign(m+1,0);
        for(int i=0;i<n;i++)c[rk[i]=s[i]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int i=0;i<n;i++)sa[--c[s[i]]]=i;

        for(int w=1;;w<<=1)
        {
            m=RadixSort(m,w);
            if(m+1>=n)break;
        }
//        for(int i=0;i<n;i++)printf("%d ",rk[i]);puts("");
        for(int i=0,k=0;i<n;i++)
        {
            if(rk[i]==0)continue;
            if(k)k--;
            while(i+k<n&&sa[rk[i]-1]+k<n&&s[i+k]==s[sa[rk[i]-1]+k])k++;
            height[rk[i]]=k;
        }
//        for(int i=0;i<n;i++)printf("%d ",height[i]);puts("");
        for(int i=n-1;i>=0;i--)
        {
            nex[i].assign(31,n);
            nex[i][0]=height[i];
            for(int j=1,w=2;i+w-1<n;j++,w<<=1)nex[i][j]=min(nex[i][j-1],nex[i+w/2][j-1]);
        }
    }
    int RadixSort(int m,int w) {
        c.assign(m+1,0);
        static vector<int>tmp; tmp.resize(n);
        static vector<int>oldrk; oldrk=rk;

        int p=0;
        for(int i=n-1;i>=max(0,n-w);i--)tmp[p++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=w)tmp[p++]=sa[i]-w;

        for(int i=0;i<n;i++)c[rk[i]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--)sa[--c[rk[tmp[i]]]]=tmp[i];

        auto neq=[&](int i,int j,int w){
            if(oldrk[i]!=oldrk[j])return true;
            int rki=i+w<n?oldrk[i+w]:-1;
            int rkj=j+w<n?oldrk[j+w]:-1;
            return rki!=rkj;
        };
        p=0;
        rk[sa[0]]=0;
        for(int i=1;i<n;i++)rk[sa[i]]=neq(sa[i],sa[i-1],w)?++p:p;
        return p;
    }
    int LCP(int x,int y)
    {
        int ret=n-x;
        x=rk[x],y=rk[y];
        if(x>y)swap(x,y);
        x++;
        for(int j=30;j>=0;j--)
        {
            if(x+(1<<j)-1>y)continue;
            ret=min(ret,nex[x][j]);
            x+=1<<j;
        }
        return ret;
    }
};
ll d[MAX],len[MAX];
vector<int>e[MAX];
int solve()
{
    int n;
    string s;
    cin>>n>>s;
    string rs=s;
    reverse(rs.begin(),rs.end());

    SA sa(s+"$"+rs+"@");
    ll tot=0;
    for(int i=0;i<n;i++)
    {
        int even=sa.LCP(i,2*n-i+1);
        d[i-even]+=1;
        d[i]-=1;
        d[i+1]-=1;
        d[i+even+1]+=1;
        if(i-even-1>=0&&i+even<n)
        {
            e[i-even-1].push_back(i+even);
            e[i+even].push_back(i-even-1);
        }

        int odd=sa.LCP(i,2*n-i);
        d[i-odd+1]+=1;
        d[i+1]-=2;
        d[i+odd+1]+=1;
        len[i]=odd;
        tot+=even+odd;
        if(i-odd>=0&&i+odd<n)
        {
            e[i-odd].push_back(i+odd);
            e[i+odd].push_back(i-odd);
        }
    }
    for(int i=1;i<n;i++)d[i]+=d[i-1];
    for(int i=1;i<n;i++)d[i]+=d[i-1];
    ll ans=tot,idx=0,gt=0;
    for(int i=0;i<n;i++)
    {
        for(char c='a';c<='z';c++)
        {
            ll cur=tot-d[i]+len[i];
            if(c==s[i])continue;
            for(int j:e[i])
            {
                if(s[j]!=c)continue;
                if(j>i)cur+=1+sa.LCP(j+1,2*n-i+1);
                else cur+=1+sa.LCP(i+1,2*n-j+1);
            }
            if(cur<ans)continue;
            if(cur>ans){ans=cur,idx=i,gt=c-s[i];continue;}
            if(idx==i&&gt<c-s[i])continue;
            if(idx!=i&&(gt<0||(gt==0&&c>=s[i])))continue;
            ans=cur,idx=i,gt=c-s[i];
        }
    }
    s[idx]+=gt;
    cout<<ans<<endl;
    cout<<s<<endl;
    return 0;
}
int main()
{
    int T=1;
//    cin>>T;
    while(T--)solve();
    return 0;
}