题意：

定义一种字符串gray串满足：

1.长度为奇数

2.正中间的字母只出现一次

3.左右两端相同，左右两端也是gray串

一个gray串的贡献为这个串长度的平方

现给你一个长为n的字符串，你可以修改至多一个字母，使得总贡献值最大

(n<=1e5)

Solution:

可以发现gray串的长度是倍增的，所以最多有log种不同长度的gray串，这样的话我们可以考虑串中每个位置的贡献，这种贡献可以类似倍增预处理求出，然后我们再处理 val[i][j] v a l [ i ] [ j ] 表示如果第i位为j会产生多少贡献，最后把修改后贡献和初始贡献相减即为可能的变化贡献

可能val数组不好处理，这里简单描述一下，具体细节大家还是看代码好了：

枚举从每个位置开始的不同长度的字符串，如果要改变一个字符使其变成gray串，分为两种情况：

1.改中间：枚举中间字母，判断两边是否合法即可

2.改左或者改右：如果能变成gray串说明左右只相差1个字母，求出这个不同的位置即可，代码里使用了求两次LCP的方式

总复杂度 O(26∗nlogn) O ( 26 ∗ n log ⁡ n )

极其练习代码能力QwQ

代码（注意这道题卡常，哈希需要使用自然溢出，取模会T）：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
const int bas=211;
unsigned long long ha[N],mi[N];
int num[N][26];
int a[N];
int n,len[30];
bool gray[N][30];
long long val[N][26],cost[N],ans;
int maxlog;
char s[N];
bool pan(int l1,int l2,int le)
{
    int r1=l1+le-1,r2=l2+le-1;
    if (r1>n||r2>n) return 0;
    unsigned long long s1=ha[r1]-ha[l1-1]*mi[r1-l1+1];
    unsigned long long s2=ha[r2]-ha[l2-1]*mi[r2-l2+1];
    return s1==s2;
}
void judge(int l,int k)
{
    if (k==1) {gray[l][k]=1;return;}
    int mid=l+len[k-1],r=l+len[k]-1;
    if ((num[r][a[mid]]-num[l-1][a[mid]]==1)&&pan(l,mid+1,len[k-1])&&gray[l][k-1]&&gray[mid+1][k-1])
        gray[l][k]=1;
    return;
}
int LCP(int l1,int l2)
{
    int le=0;
    for (int i=maxlog;i>=0;i--)
        if (pan(l1+le,l2+le,(1<<i))) le+=(1<<i);
    return le;
}
void calc(int l,int k)
{
    int r=l+len[k]-1,mid=l+len[k-1];
    if (k==1) {
  for (int i=0;i<26;i++) if (a[l]!=i) val[l][i]++;return;}
    if (pan(l,mid+1,len[k-1])&&gray[l][k-1]&&gray[mid+1][k-1])
    {
        for (int i=0;i<26;i++)
            if (a[mid]!=i&&num[r][i]-num[l-1][i]==0) val[mid][i]+=1ll*len[k]*len[k];
    }
    int l1=l,l2=mid+1;
    int lcp=LCP(l1,l2);
    if (lcp>=len[k-1]) return;
    if (l1+lcp+1+LCP(l1+lcp+1,l2+lcp+1)<mid) return;
    if (gray[l2][k-1]&&num[r][a[mid]]-num[mid][a[mid]]==0) val[l1+lcp][a[l2+lcp]]+=1ll*len[k]*len[k];
    if (gray[l1][k-1]&&num[mid-1][a[mid]]-num[l-1][a[mid]]==0) val[l2+lcp][a[l1+lcp]]+=1ll*len[k]*len[k];
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    mi[0]=1;
    for (int i=1;i<=n;i++)
    {
        a[i]=s[i]-'a';
        num[i][a[i]]++;
        for (int j=0;j<26;j++) num[i][j]+=num[i-1][j];
        mi[i]=mi[i-1]*bas;
        ha[i]=ha[i-1]*bas+s[i];
    }
    for (int i=1;i<=30;i++)
    {
        len[i]=len[i-1]*2+1;
        if (len[i]>n) {maxlog=i-1;break;}
    }
    for (int i=1;i<=maxlog;i++)
        for (int j=1;j<=n;j++)
        {
            if (j+len[i]-1>n) break;
            judge(j,i);
            if (gray[j][i]) ans+=1ll*len[i]*len[i],cost[j]+=1ll*len[i]*len[i],cost[j+len[i]]-=1ll*len[i]*len[i];
        }
    for (int i=1;i<=n;i++) cost[i]+=cost[i-1];
    for (int i=1;i<=maxlog;i++)
        for (int j=1;j<=n;j++)
        {
            if (j+len[i]-1>n) break;
            calc(j,i);
        }
    long long sum=0;
    for (int j=1;j<=n;j++)
        for (int k=0;k<26;k++)
            sum=max(sum,-cost[j]+val[j][k]);
    printf("%I64d",sum+ans);
}