给出一个\(5000\)长的字符串 判断有多少个连续子串是超级回文的。
这里超级回文的定义是将字符串分成\(2k\)段每段按照回文对应相等。
设\(f_{l,r}\)表示区间\(l,r\)是否是符合要求的。引入\(border\)的定义：最长的前缀和后缀匹配长度。
容易想到我们如果暴力枚举每个区间来判断该区间\(l,r\)是否合法，然后枚举该区间的最后一段长度\(k\)加以判断再加上\(f_{l+k,r-k}\)的状态即可判断。利用区间dp可以达到\(n^3\)
继续思考这最后一段的匹配本质上是当前区间子串的一个\(border\)。
如果我们固定左端点，右端点在向右移动的过程中是可以维护出\(KMP\)的\(nex\)数组的，有了\(nex\)数组我们就可以快速得到当前的所有\(border\)
倒序枚举左端点可以完成上述操作，利用\(KMP\)的\(nex\)数组得到\(border\)来判断。
这样最坏的复杂度还是\(n^3\)的，队友猜测如果该串是合法的那么最小的\(border\)可以令其合法。
实际上更全面的结论是该串是合法的那么任意一个\(\le \frac{len}{2}\)的\(border\)均可使其合法。
如果是前者赛时我的做法是利用fail树来找到最小的\(border\)
后者直接两次\(KMP\)就可以求出\(\le \frac{len}{2}\)的最大的\(border\)。
接下来是证明：
设当前区间为\([l,r]\)若区间合法则存在一个最后一个分割\(k\)满足\([k,l+k,r-k,k]\)这是一个合法分割。接下来设最小的\(border\)为\(w\)那么我们有\([w,k-w,l+k,r-k,k-w,w]\)想办法使这样的一种划分合法首先若\(w\ge \frac{k}{2}\)那么这\(k\)个字符其实是全部相同的。反之，先让最后的\(w\)个先匹配上，\(l+r,r-k\)这个区间本身就是合法的我们可以不用管，此时有\([k-w,k-w]\)要匹配上显然有\(k-2w,w,w,k-2w\)匹配证毕。
最大的\(border\)也可以类似证明。
这里放利用最小的\(border\)的代码。还有一个结论是一个字符串的最小\(border\le \frac{len}{2}\)
//#include<bits/stdc++.h>
#include<iomanip>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<ctime>
#include<cstring>
#include<utility>
#include<vector>
#define MAXN 5010
#define sc(x) scanf("%d",&x)
#define pb push_back
#define rep(a,b,k) for(int k=a;k<=b;++k)
using namespace std;
int n,m,T;
char a[MAXN];
int f[MAXN][MAXN];
int w[MAXN][MAXN];
int fa[MAXN];
int nex[MAXN];
int main()
{
//freopen("1.in","r",stdin);
sc(T);
while(T--)
{
scanf("%s",a+1);
int now;
int ans=0;
n=strlen(a+1);
for(int l=n-1;l>=1;--l)
{
rep(1,n,j)fa[j]=j;
rep(l,n,r)
{
fa[r]=r;
f[l][r]=0;
if(l==r)
{
nex[l]=now=l-1;
nex[now]=l-1;
fa[l-1]=l-1;
continue;
}
while(now!=l-1&&a[now+1]!=a[r])now=nex[now];
if(a[now+1]==a[r])++now;
else now=l-1;
nex[r]=now;
if(nex[r]!=l-1)fa[r]=fa[nex[r]];
if((r-l+1)&1)continue;
if(nex[r]!=l-1)
{
int cc=fa[r]-l+1;
if(cc<<1==r-l+1)f[l][r]=1;
else f[l][r]|=f[l+cc][r-cc];
}
ans+=f[l][r];
}
}
printf("%d\n",ans);
}
return 0;
}