fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int P = 8521,mod = 1000000007;
  4. unsigned long t[444444],f[444444];
  5. void build(string s,int v,int tl,int tr){
  6. 	if(tl==tr)t[v]=(t[v]*P)+(s[tl]-48);
  7. 	else {
  8. 		int tm=(tl+tr)>>1;
  9. 		build(s,v*2,tl,tm);
  10. 		build(s,v*2+1,tm+1,tr);
  11. 		t[v]=(t[v*2]+t[v*2+1])*P;
  12. 		t[v]%=mod;
  13. 	}
  14. }
  15. void build2(string s,int v,int tl,int tr){
  16. 	if(tl==tr)f[v]=(f[v]*P)+(s[tl]-48);
  17. 	else {
  18. 		int tm=(tl+tr)>>1;
  19. 		build2(s,v*2,tl,tm);
  20. 		build2(s,v*2+1,tm+1,tr);
  21. 		f[v]=(f[v*2]+f[v*2+1])*P;
  22. 		f[v]%=mod;
  23. 	}
  24. }
  25. unsigned long geth(int v,int tl,int tr,int l,int r){
  26. 	if(l>r)return 0;
  27. 	if(tl==l && tr==r)return t[v]%mod;
  28. 	else {
  29. 		int tm=(tl+tr)>>1;
  30. 		return (geth(v*2,tl,tm,l,min(r,tm))+geth(v*2+1,tm+1,tr,max(l,tm+1),r))*P;
  31. 	}
  32. }
  33. unsigned long getf(int v,int tl,int tr,int l,int r){
  34. 	if(l>r)return 0;
  35. 	if(tl==l && tr==r)return f[v]%mod;
  36. 	else {
  37. 		int tm=(tl+tr)>>1;
  38. 		return (geth(v*2,tl,tm,l,min(r,tm))+geth(v*2+1,tm+1,tr,max(l,tm+1),r))*P;
  39. 	}
  40. }
  41. int n;
  42. int solve(int l,int r){
  43. 	if(l==r)return 1;
  44. 	unsigned a1,a2;
  45. 	a1=geth(1,0,n-1,l,r);
  46. 	a2=getf(1,0,n-1,l,r);
  47. 	a1%=mod;
  48. 	a2%=mod;
  49. 	return (a1==a2);
  50. }
  51. int main(){
  52. 	cin.tie(NULL);
  53. 	ios_base::sync_with_stdio(0);
  54. 	int k;
  55. 	long long ans=0;
  56. 	string r;
  57. 	cin>>k;
  58. 	cin>>r;
  59. 	n=(int)r.size();
  60. 	build(r,1,0,n-1);
  61. 	string s=r;
  62. 	reverse(r.begin(),r.end());
  63. 	build2(r,1,0,n-1);
  64. 	bool g=0;
  65. 	for(int i=0;i<n;i++){
  66. 		for(int j=0;j<n;j++){
  67. 			if(j-i==k-1 && i<=j){
  68. 				g=solve(i,j);
  69. 				ans+=g;
  70. 			}
  71. 		}
  72. 	}
  73. 	cout<<ans<<"\n";
  74. return 0;}
Success #stdin #stdout 0s 6908KB
comments (?)
stdin
copy 
5
ababab
stdout
copy 
2
https://ideone.com/waWCXD
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!