哈希或者manacher·改。。我写manacher
manacher在拓展的时候改一下判断条件就好了。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define ll long long 6 using namespace std; 7 const int maxn=5e5+23; 8 char s1[maxn]; 9 int s[maxn<<1],p[maxn<<1]; 10 ll ans; 11 int i,j,k,n,m; 12 13 int ra;char rx; 14 inline int read(){ 15 rx=getchar(),ra=0; 16 while(rx<'0'||rx>'9')rx=getchar(); 17 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 18 } 19 int main(){ 20 n=read(); 21 scanf("%s",s1+1); 22 for(s[0]='%',s[1]='#',i=1;i<=n;i++)s[i<<1]=s1[i]-'0',s[i<<1|1]='#'; 23 n=n<<1|1;s[n+1]='^'; 24 int mx=0,id=0; 25 for(i=1;i<=n;i++){ 26 if(mx>i)p[i]=min(mx-i,p[id-(i-id)]); 27 while(s[i-p[i]]+s[i+p[i]]==1||s[i-p[i]]+s[i+p[i]]=='#'+'#')p[i]++; 28 if(i+p[i]>mx)mx=i+p[i],id=i; 29 ans+=p[i]>>1; 30 } 31 printf("%lld ",ans); 32 } 33