哈希 or Manacher
首先有一个很显然的结论
对于一个回文串s
每次从s的中心开始向左右扩展一步
每次扩展的串一定都是回文串
如 s=abccba
从s的中心左右扩展一步得到 cc
扩展两步得到 bccb
扩展三步就得到了 abccba = s
所以如果我们枚举中心
向左右扩展，找到最长的回文串 s
那么只要 ans += len_s/2 就能得到所有的回文子串的数量
找最长长度要用二分
判断回文的话用哈希就行了
取反的问题在预处理后缀哈希时就可以搞定了
具体实现还是看代码吧
复杂度O(n log n)
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef unsigned long long ull;//自然溢出 const int N=1e6+7; const int base=23333; int n; long long ans;//答案一定要用long long 存！！！ ull h1[N],h2[N],fac[N];//前缀哈希，后缀哈希，fac[i]存base^i char ch[N]; int main() { cin>>n; scanf("%s",ch+1); fac[0]=1; for(int i=1;i<=n;i++) { fac[i]=fac[i-1]*base; h1[i]=h1[i-1]*base+(ch[i]=='1');//预处理前缀哈希 } for(int i=n;i;i--) h2[i]=h2[i+1]*base+(ch[i]=='0');//后缀哈希预处理时取反 for(int i=1;i<n;i++)//枚举中点 { int l=0,r=min(i,n-i),mid;//二分长度 while(l<r) { mid=l+ ((r-l)>>1) +1; ull hs1=h1[i+mid]-h1[i-mid]*fac[mid*2],hs2=h2[i-mid+1]-h2[i+mid+1]*fac[mid*2]; //取出子串哈希值 if(hs1==hs2) l=mid; else r=mid-1; } ans+=l;//更新答案 } cout<<ans; return 0; }
然后讲讲Manacher（应该都懂Manacher吧..）
预处理完字符串后，就只要找以 '#' 为中心的回文就好了
我们可以得到每个以 '#' 为中心的最长回文长度，然后就可以像哈希的方法一样更新答案了
复杂度O(n)
// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int N=1e6+7; int n,a[N<<1],f[N],mx,pos; long long ans; char s[N]; int main() { cin>>n; scanf("%s",s+1); n=n*2+1; for(int i=1;i<=n;i++) { if(i&1) a[i]=-1;//相当于'#' else a[i]=s[i>>1]-'0'; //就是爱把字符转数字.. } for(int i=1;i<=n;i++) { if(a[i]!=-1) continue;//只要找以'#'为中心的回文 if(i<mx) f[i]=min(mx-i,f[(pos<<1)-i]); else f[i]=1;//Manacher核心 while(1) { if(a[i+f[i]]==-1) { f[i]++; continue; //对'#'特判一下 } if(a[i+f[i]]==a[i-f[i]] || i-f[i]<1 || i+f[i]>n) break; f[i]++;//暴力判断 } if(i+f[i]>mx) mx=i+f[i],pos=i; ans+=((f[i]-1)>>1);//更新 } cout<<ans; return 0; }