\(\color{purple}\text{Palindrome Partition}\)
该说不难，只待一切走上正轨。
显然我们不能枚举每个子串，所以我们考虑枚举以 \(i\) 结尾的“好的”子串的个数。代价是我们得保证不会有重复，因为同一个子串例如：“BBAABB”，可以来自“BBAA+BB”，也可以来自“BB+AABB”，我们统一规定，一个“好的”子串来自另一个“好的”子串加上最短的偶数回文子串，这样便可以避免重复。
设 \(f[i]\) 表示以 \(i\) 结尾的“好的”子串数目，因为是加上最短偶数回文子串，我们假设以 \(i\) 结尾的最短偶数回文子串长度为 \(len\) ，则： \(f[i]=f[i-len]+1\) 。
现在只要求 “以 \(i\) 结尾的最短偶数回文子串长度”。回文想到用 \(Manacher\) ，偶数子串所以只考虑 中间\(\#\) 的回文半径，假设为 \(r[i]\) ，显然对 \([i,i+r[i]-1]\) 中的字符一个个处理太慢，我们需要区间处理，想到线段树，而这个区间统一的信息是什么：长度吗？显然不是。我们发现其实这些回文串的中点是一样的，又发现其实对于以 \(i\) 为结尾的回文子串中，回文中点越靠后，长度越短。所以只需用线段树维护每个点为结尾的回文子串的最靠后的中点。
最后是一些实现的细节，线段树可以标记永久化，短，好写。而写 \(Manacher\) 时要不停地在加入 \(\#\) 的新串 \(s2\) 和原串 \(s1\) 之间来回转换，写的时候可以放个样例在旁边，对着写，就不会想蒙圈了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+110;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int T,n,m,r[N],ans,len[N],f[N];char s1[N],s2[N];
struct SegmentTree{
int lazy[N<<1];
void update(int u,int l,int r,int L,int R,int va){
if(L<=l && r<=R){
lazy[u]=max(lazy[u],va);
return;
}
int mid=(l+r)>>1;
if(L<=mid)update(u<<1,l,mid,L,R,va);
if(R>mid)update(u<<1|1,mid+1,r,L,R,va);
return;
}
void EndWar(int u,int l,int r,int va){
va=max(va,lazy[u]);
lazy[u]=0;
if(l==r){
if(va==0)len[l]=0;
else len[l]=l*2-va+1;
return;
}
int mid=(l+r)>>1;
EndWar(u<<1,l,mid,va),EndWar(u<<1|1,mid+1,r,va);
return;
}
}E;
void solve(){
n=read();m=0;scanf("%s",s1+1);
s2[0]='+';s2[++m]='#';int maxn=1,p=1;
for(int i=1;i<=n;i++)s2[++m]=s1[i],s2[++m]='#';
for(int i=1;i<=m;i++){
r[i]=min(maxn-i,r[2*p-i]);
while(s2[i-r[i]]==s2[i+r[i]])r[i]++;
if(i+r[i]>maxn)maxn=i+r[i],p=i;
}
for(int i=1;i<=m;i+=2)
if(r[i]>1)E.update(1,1,n,(i+1)/2,min((i+r[i]-2)/2,n),i);
E.EndWar(1,1,n,0);
// for(int i=1;i<=n;i++)cout<<len[i]<<" ";cout<<endl;
for(int i=1;i<=n;i++){
if(len[i]){
f[i]=1+f[i-len[i]];
}
else f[i]=0;
}
long long ans=0;
for(int i=1;i<=n;i++)
ans+=f[i];
printf("%lld\n",ans);
return;
}
int main(){
T=read();while(T--)solve();
return 0;
}
/*
1
12
accabccbacca
*/