fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define len(s) (int)s.size()
  4. #define pb push_back
  5. #define fi first
  6. #define se second
  7. #define MASK(x) ((1LL)<<(x))
  8. #define BIT(x,i) (((x) >>(i))&(1LL))
  9. #define ii pair<int,int>
  10. #define OpenFile(Name) if (fopen(Name".inp", "r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  11. using namespace std;
  12.  
  13. int dx[4]={0,1,0,-1};
  14. int dy[4]={1,0,-1,0};
  15.  
  16. ll K=1e18,MOD=1e9+7;
  17. const int N=1e6+5,M=5e3+3,base=31;
  18.  
  19. ///____________________________________________________________________________________________________________________________
  20.  
  21.  
  22.  
  23.  
  24. int dp[M][M];
  25. ll res[M];
  26.  
  27. int main() {
  28.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  29.     OpenFile("TASK");
  30.  
  31.  
  32.     string s; cin>>s;
  33.     int n=len(s);
  34.  
  35.  
  36.     for (int k=1;k<=n;++k) {
  37.         for (int l=0;l<n-k+1;++l) {
  38.             int r=l+k;
  39.  
  40.             if (k==1) {
  41.                 dp[l][r]=1;
  42.                 continue;
  43.             } else
  44.             if (k==2) {
  45.                 if (s[l]==s[r-1]) dp[l][r]=2;
  46.                 continue;
  47.             }
  48.  
  49.             if (s[l]!=s[r-1] || !dp[l+1][r-1]) continue;
  50.  
  51.             int m=(l+r)>>1;
  52.             dp[l][r]=1;
  53.             if (k&1) {
  54.                 if (dp[l][m] && dp[m+1][r]) dp[l][r]=dp[l][m]+1;
  55.             } else
  56.                 if (dp[l][m] && dp[m][r]) dp[l][r]=dp[l][m]+1;
  57.         }
  58.     }
  59.  
  60.     for (int k=1;k<=n;++k)
  61.     for (int l=0;l<n-k+1;++l) res[dp[l][l+k]]++;
  62.  
  63.  
  64.     for (int i=n-1;i>=1;--i) res[i]+=res[i+1];
  65.     for (int i=1;i<=n;++i) cout<<res[i]<<' ';
  66.  
  67.  
  68.  
  69.     cerr<<"\nBien dich thanh cong\nTime: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s";
  70.     return 0;
  71. }
  72.  
  73.  
Success #stdin #stdout #stderr 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Bien dich thanh cong
Time: 0.007235 s
https://ideone.com/sdRH8l
language:
C++14 (clang 8.0)
created:
3 days 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!