fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MOD = 1e9+9;
  4. const int MAX = 5007;
  5. #define ll long long int
  6. ll sm = 0;
  7.  
  8. vector<int> power(10000);
  9. int n;
  10.  
  11. int get_hash(int l,int r,vector<int> &hash,int type){
  12.  
  13. 	if(type == 0) return (hash[r] - power[r-l+1]*(l-1>=0 ? hash[l-1] : 0) + MOD)%MOD; 
  14. 	else return (hash[l] - power[r-l+1]*(r+1<=n-1 ? hash[r+1] : 0) + MOD)%MOD; 
  15. }
  16.  
  17.  
  18. void solve(string s){
  19.  
  20.     n = s.length();
  21.     int p = 31;
  22. 	vector<int> res(n,0);
  23.  
  24. 	int pw = 1;
  25. 	power[0] = 1;
  26.  
  27. 	vector<int> fr(n,1),bw(n,1);
  28. 	fr[0] = (s[0] -  'a' + 1);
  29. 	bw[n-1] = (s[n-1] -  'a' + 1);
  30. 	for(int i = 1;i<n;i++){
  31.  
  32. 		pw = (pw*p)%MOD;
  33. 		power[i] = pw;
  34. 		fr[i] = (fr[i-1] + ((s[i] - 'a'+1)*pw)%MOD)%MOD; 
  35. 		bw[i] = (bw[n-1-i] + ((s[n-1-i] - 'a'+1)*pw)%MOD)%MOD; 
  36. 	}
  37.  
  38.  
  39. 	map<int,int> hmap;
  40. 	for(int i = 0;(1<<i)<=n;i++){
  41.  
  42. 		int len = (1<<i);
  43.  
  44. 		for(int j = 0;j<n;j++){
  45.  
  46. 			if(j+len-1>=n) continue;
  47.  
  48. 			int h1 = get_hash(j,j + (len-1)/2,fr,0); 
  49. 			int h2 = get_hash(j + (len-1)/2 + 1,j+len-1,bw,1); 
  50.  
  51. 			if(h1 == h2) hmap[len]++;
  52. 		}
  53. 	}
  54.  
  55. 	int sm = 0,i = 0;
  56. 	for(auto &m : hmap) sm+=(m.second);
  57.  
  58. 	for(auto &m : hmap){
  59.  
  60. 		res[i] = sm;
  61. 		sm-=m.second;
  62. 		i++;	
  63. 	}
  64.  
  65. 	for(int j =0;j<n;j++) cout<<res[i]<<" ";
  66.  
  67. }
  68.  
  69. int main(){
  70.  
  71. 	ios_base::sync_with_stdio(false);
  72. 	cin.tie(0);  cout.tie(0);
  73.  
  74. 	string s;
  75. 	cin>>s;
  76. 	solve(s);
  77.  
  78. 	return 0;
  79. }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
abacaba
stdout
copy 
0 0 0 0 0 0 0
https://ideone.com/FaOlfO
language:
C++14 (gcc 8.3)
created:
3 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!