题解：P16606 [SYSUCPC 2025] Palindrome

· · 题解

题意简述

给定长度不超过 5\times 10^5 的小写字符串 T。

准回文串不包含长度至少为 2 的回文子串。它还能通过一次区间翻转变成回文串。求 T 中准回文子串的数量。

解题思路

任意长度至少为 4 的回文串删去首尾字符后仍是回文串。不断删除后，总能得到长度为 2 或 3 的回文串。

因此，第一个条件等价于：相邻字符不同，距离为 2 的字符也不同。

按这两个条件把原串分成极长合法段。遇到相邻字符相同时，新段从当前字符开始；遇到距离为 2 的字符相同时，新段从前一个字符开始。长度至少为 2 的合法子串恰好属于一个合法段，单字符则统一计入答案。

设 A 为非空字符串，S 为任意字符串，x 为单个字符。能通过一次区间翻转变成回文串的字符串恰好具有以下四种形式：

\begin{aligned} & S+A+A+\operatorname{rev}(S) \\ & S+x+A+A+\operatorname{rev}(S) \\ & S+A+x+A+\operatorname{rev}(S) \\ & S+A+A+x+\operatorname{rev}(S) \end{aligned}

第一种长度为偶数，其余三种长度为奇数。逐对删除原串两端已经对称的字符，再考察翻转区间与中心的位置，便会得到这四种形式。反向验证也成立。依次翻转第一个 A、x+A、第一个 A 或第二个 A 与 x，所得字符串都是回文串。

奇数长度可能存在多种划分。把中间部分记为 M，不断把 M 两端相同的字符移入 S 与 \operatorname{rev}(S)，直到 M 两端不同。若 M=x+A+A 或 M=A+A+x，一次移动后会转化为 A+x+A。若 M=A+x+A，两端相同会使 x 两侧出现长度为 3 的回文串。因此，这种划分存在且唯一。

下面用广义 Runs 统一寻找 A+A 与 A+x+A。称极长的 p 周期区间 [l,r] 为广义 Run，当且仅当 r-l+1\ge 2p-1。

枚举周期 p 和相邻的两个分块起点 j,j+p。设它们向左的最长公共后缀长度为 a，向右的最长公共前缀长度为 b。当 a+b\ge p-1 时，得到广义 Run [j-a,j+p+b-1]。相同区间仅保留最小周期。

最长公共前缀使用后缀数组与稀疏表查询。把合法段 s 与 \operatorname{rev}(s) 拼接，便能同时得到向左和向右的匹配长度。

对一个广义 Run [l,r]，枚举 d=p,2p,\dots。

对于 A+A，有 |A|=d。可行起点为 [l,r-2d+1]。若起点严格位于区间内部，外层 S 只能为空。否则，相邻周期字符会要求合法段中两个相邻字符相同。

边界起点可以向外扩展。设核心为 [a,b]，在拼接串上查询右侧与左侧倒序的最长公共前缀。合法的扩展数量为：

1+\min(a-1,n-b,\operatorname{lcp}(b+1,2n-a+2))

其中 1 对应 S 为空。核心两端必须不同，否则不满足奇数情形的唯一划分；偶数情形下，这一点由合法段在两个 A 的交界处相邻字符不同保证。

对于 x+A+A 和 A+A+x，字符 x 只能紧贴 Run 的左边界或右边界。若 Run 还能沿该方向延伸，M 的两端便相同，不是唯一划分。故分别检查左右边界即可。

对于 A+x+A，周期距离为 d=|A|+1，核心长度为 2d-1。可行起点为 [l,r-2d+2]。距任一边界不超过 1 的四个起点用最长公共前缀求扩展量。其他起点恰好能取 |S|=0 或 |S|=1。周期性保证第一层匹配，距离为 2 的字符不同会阻止第二层匹配。

设合法段长度为 n。后缀数组和稀疏表预处理为 O(n\log n)。广义 Run 的枚举为 O(n\log n)，对周期倍数的统计为 O(n\log^2 n)。空间复杂度为 O(n\log n)。所有合法段的长度之和为 O(|T|)，总复杂度仍为 O(|T|\log^2|T|)。

正确性证明

任意较长回文串的中心都包含长度为 2 或 3 的回文串。因此，第一个条件等价于不存在相邻相同字符和距离为 2 的相同字符。分段后，任何跨过断点的较长子串都包含对应冲突。距离为 2 的断点仅需把前一个字符带入新段。故每个长度至少为 2 的合法子串恰好在一个合法段中出现。

设一次翻转把字符串变成回文串。由两端向中心删除未受影响的对称字符。剩余翻转区间必然接触剩余串的一端。根据长度奇偶与中心字符的位置，剩余串分别为 A+A、x+A+A、A+x+A 或 A+A+x。加回删除的字符后，便得到四种形式。每种形式也有对应的合法翻转，所以分类不重不漏。

对奇数长度，不断把中间部分的相同首尾移入外层。该过程每次使中间部分缩短 2，所以必然终止。x+A+A 和 A+A+x 在移动后转化为 A+x+A；后者两端不能相同，否则中心附近出现长度为 3 的回文串。因此，每个奇数准回文串具有唯一的两端不同核心。

任意 A+A 都具有周期 |A|，任意 A+x+A 都具有周期 |A|+1。把周期向两侧极大扩展，便得到对应广义 Run。枚举相邻分块并计算最长公共后缀与最长公共前缀，会恢复这个极大区间。保留最小周期后，周期引理保证所有可行距离 d 都是最小周期的倍数。因此，倍数枚举不会遗漏核心。

考虑 A+A 的内部起点。若 S 非空，第一对待匹配字符会因周期性变成相邻字符。这违反第一个条件，所以仅有空扩展。边界起点的最长公共前缀逐层比较 S 与右侧倒序，因而算出全部扩展。x+A+A 的唯一核心只能位于 Run 左边界。A+A+x 则只能位于右边界。

对于 A+x+A，内部起点的第一层扩展由周期性保证。第二层会比较距离为 2 的字符，所以不能继续。四个靠近边界的起点改用最长公共前缀处理，覆盖全部例外。边界起点先去重，奇数核心又具有唯一划分，因此不同贡献不会重复。

综上，算法对每个准回文子串计数一次，且不会计入不满足条件的子串，所得答案正确。

参考代码

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

using ll=long long;
const int N=1000005;
char t[N];
int n;
ll ans;
struct SA
{
    int len;
    int x[N],y[N],cnt[N],sa[N],rk[N],lg[N];
    int h[20][N];
    void build(char s[],int sz)
    {
        len=sz;
        int *a=x,*b=y;
        int m=26;
        fill(cnt,cnt+m+1,0);
        for(int i=1;i<=sz;i++)cnt[a[i]=s[i]-'a'+1]++;
        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=sz;i>=1;i--)sa[cnt[a[i]]--]=i;
        for(int k=1;k<sz;k<<=1)
        {
            int top=0;
            for(int i=max(1,sz-k+1);i<=sz;i++)b[++top]=i;
            for(int i=1;i<=sz;i++)if(sa[i]>k)b[++top]=sa[i]-k;
            fill(cnt,cnt+m+1,0);
            for(int i=1;i<=sz;i++)cnt[a[i]]++;
            for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
            for(int i=sz;i>=1;i--)sa[cnt[a[b[i]]]--]=b[i];
            swap(a,b);
            a[sa[1]]=1;
            int tot=1;
            for(int i=2;i<=sz;i++)
            {
                int u=sa[i-1],v=sa[i];
                if(b[u]==b[v]&&(u+k>sz?0:b[u+k])==(v+k>sz?0:b[v+k]))a[v]=tot;
                else a[v]=++tot;
            }
            m=tot;
            if(m==sz)break;
        }
        for(int i=1;i<=sz;i++)rk[sa[i]]=i;
        int lcp=0;
        for(int i=1;i<=sz;i++)
        {
            if(rk[i]==1)
            {
                lcp=0;
                continue;
            }
            if(lcp)lcp--;
            int j=sa[rk[i]-1];
            while(i+lcp<=sz&&j+lcp<=sz&&s[i+lcp]==s[j+lcp])lcp++;
            h[0][rk[i]]=lcp;
        }
        lg[1]=0;
        for(int i=2;i<=sz;i++)lg[i]=lg[i>>1]+1;
        for(int i=1;(1<<i)<=sz;i++)
        {
            for(int j=2;j+(1<<i)-1<=sz;j++)h[i][j]=min(h[i-1][j],h[i-1][j+(1<<(i-1))]);
        }
    }
    int lcp(int i,int j)
    {
        if(i==j)return len-i+1;
        i=rk[i];
        j=rk[j];
        if(i>j)swap(i,j);
        int k=lg[j-i];
        return min(h[k][i+1],h[k][j-(1<<k)+1]);
    }
}suf;
void add(int l,int r)
{
    if(t[l]==t[r])return;
    int len=min({l-1,n-r,suf.lcp(r+1,2*n-l+2)});
    ans+=len+1;
}
void solve(const string &s)
{
    n=s.size();
    if(n<2)return;
    int pos=0;
    for(auto c:s)t[++pos]=c;
    for(int i=1;i<=n;i++)t[n+i]=t[n-i+1];
    suf.build(t,2*n);
    unordered_set<ll> vis;
    vis.reserve(static_cast<size_t>(2*n));
    for(int i=2;i<=(n+1)/2;i++)
    {
        for(int j=1;j+i<=n+1;j+=i)
        {
            int lc=min(j-1,suf.lcp(2*n-j+2,2*n-j-i+2));
            int rc=min(n-j-i+1,suf.lcp(j,j+i));
            if(lc+rc<i-1)continue;
            int l=j-lc,r=j+i+rc-1;
            if(!vis.insert(((ll)l<<32)|r).second)continue;
            for(int k=i;2*k<=r-l+1;k+=i)
            {
                int p=r-2*k+1;
                add(l,l+2*k-1);
                if(p!=l)add(p,r);
                ans+=max(0,p-l-1);
                if(l>1)add(l-1,l+2*k-1);
                if(r<n)add(p,r+1);
            }
            for(int k=i;2*k-1<=r-l+1;k+=i)
            {
                int p=r-2*k+2;
                int q[4]={l,l+1,p-1,p};
                sort(q,q+4);
                int pre=0;
                for(auto x:q)
                {
                    if(x!=pre&&l<=x&&x+2*k-2<=r)add(x,x+2*k-2);
                    pre=x;
                }
                ans+=(ll)max(0,p-l-3)*2;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    string cur;
    for(char c:s)
    {
        ans++;
        if(!cur.empty()&&cur.back()==c)
        {
            solve(cur);
            cur=c;
        }
        else if(cur.size()>1&&cur[cur.size()-2]==c)
        {
            solve(cur);
            cur=cur.back();
            cur+=c;
        }
        else
        {
            cur+=c;
        }
    }
    solve(cur);
    cout<<ans<<'\n';
    return 0;
}