题目链接
题目解法
首先考虑一个朴素的 \(dp\)
令 \(f_i\) 表示以 \(i\) 结尾的合法子串的个数
为了不重不漏，我们令 \(le_i\) 表示以 \(i\) 为右端点，离 \(i\) 最近的偶回文串的左端点，然后不难得到转移为 \(f_i=f_{le_i-1}+1\)
为什么不会漏？考虑以 \(i\) 为右端点，且比最短回文串长的子串一定可以拆分成若干个回文串
求 \(le_i\) 可以二分哈希求出最长的回文串 \([i-l,i+l)\)，然后线段树覆盖即可维护
时间复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=500100;
int n,seg[N<<2],f[N];
char str[N];
struct Hash{
int P;
ull p[N],h[2][N];
void build(){
p[0]=1;
F(i,1,n) p[i]=p[i-1]*P;
F(i,1,n) h[0][i]=h[0][i-1]*P+str[i];
h[1][n+1]=0;
DF(i,n,1) h[1][i]=h[1][i+1]*P+str[i];
}
ull gethash(int seq,int l,int r){
if(!seq) return h[seq][r]-h[seq][l-1]*p[r-l+1];
else return h[seq][l]-h[seq][r+1]*p[r-l+1];
}
}ha[2];
void pushdown(int x){ if(seg[x]!=-1) seg[x<<1]=seg[x<<1^1]=seg[x],seg[x]=-1;}
void modify(int l,int r,int x,int L,int R,int v){
if(L<=l&&r<=R){ seg[x]=v;return;}
pushdown(x);
int mid=(l+r)>>1;
if(mid>=L) modify(l,mid,x<<1,L,R,v);
if(mid<R) modify(mid+1,r,x<<1^1,L,R,v);
}
int le[N];
void get_seg(int l,int r,int x){
if(l==r){ le[l]=seg[x];return;}
pushdown(x);
int mid=(l+r)>>1;
get_seg(l,mid,x<<1),get_seg(mid+1,r,x<<1^1);
}
const int inf=1e9;
void work(){
n=read();scanf("%s",str+1);
ha[0].build(),ha[1].build();
F(i,1,n<<2) seg[i]=-1;
F(i,2,n){
int l=0,r=n+1;
while(l<r-1){
int mid=(l+r)>>1;
if(!(i-mid>=1&&i+mid-1<=n)){ r=mid;continue;}
if(ha[0].gethash(0,i,i+mid-1)==ha[0].gethash(1,i-mid,i-1)&&
ha[1].gethash(0,i,i+mid-1)==ha[1].gethash(1,i-mid,i-1)) l=mid;
else r=mid;
}
// cout<<"!!!"<<i<<' '<<l<<'\n';
if(l) modify(1,n,1,i,i+l-1,i);
}
get_seg(1,n,1);
// F(i,1,n) cout<<le[i]<<' ';cout<<'\n';
F(i,1,n) f[i]=0;
F(i,1,n) if(le[i]!=-1) f[i]=f[le[i]*2-i-2]+1;
LL ans=0;
F(i,1,n) ans+=f[i];
printf("%lld\n",ans);
}
int main(){
ha[0].P=131,ha[1].P=131;
int T=read();
while(T--) work();
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}