给定字符串 \(s\) ,求 \(s_{l,r}\) 中回文串个数。多组询问, \(|s|\leq 5000\) , \(T\leq10^5\) 。
首先介绍 \(O(n\times T)\) 的离谱做法(竟然没卡掉),先跑 \(Manachar\) ,然后暴力查询 \([l,r]\) 的回文串数量,最后用一个数组记录下来(防1 5000
数据)即可。
然后是正解,首先处理出 \(g[i][j]\) 表示 \(s_{i,j}\) 是否为回文串,然后推出 \(s_{i,j}\) 中回文串总个数 \(f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+g[i][j]\) ,最后处理一下边界。(还是只有错误复杂度的代码)。
#include<bits/stdc++.h>
using namespace std;
struct IO{
inline char read(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template <typename _Tp> inline IO & operator >> (_Tp&x){
static char c11,boo;
for(c11=read(),boo=0;!isdigit(c11);c11=read()){
if(c11==-1)return *this;
boo|=c11=='-';
}
for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
boo&&(x=-x);
return *this;
}
inline void push(const char &c) {
putchar(c);
}
template <class T>
inline void write(T x){
if (x < 0) x = -x, push('-');
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
template <class T>
inline void write(T x, char lastChar){
write(x),push(lastChar);
}
}io;
int t,slen;
int p[200005];
char s[100005];
char ss[200005];
pair<int,int> Q;
int anss[5005][5005];
int main(){
scanf("%s",s+1);
slen=strlen(s+1);
ss[0]='!',ss[2*slen+1]='#',ss[2*slen+2]='?';
for(int i=1;i<=slen;++i){
ss[2*i-1]='#';
ss[2*i]=s[i];
}
int mx=0,id=0;
for(int i=1;i<=2*slen+1;++i){
p[i]=((i>=mx)?0:min(p[2*id-i],mx-i));
while(ss[i-p[i]]==ss[i+p[i]])
++p[i];
if(i+p[i]-1>mx){
mx=i+p[i]-1;
id=i;
}
}
io>>t;
while(t--){
int ans=0;
int l,r;
io>>l>>r;
if(anss[l][r]!=0){
printf("%d\n",anss[l][r]);
continue;
}
for(int i=2*l;i<=2*r;++i){
ans+=(min(p[i],min(i-2*l+2,2*r-i+2))/2);
}
anss[l][r]=ans;
printf("%d\n",ans);
}
}
标签:ss,int,char,C20220725T3,inline,c11,回文
From: https://www.cnblogs.com/zhouzizhe/p/16642661.html