fork download
copy 
  1. //satyaki3794
  2. #include <bits/stdc++.h>
  3. #define ff first
  4. #define ss second
  5. #define pb push_back
  6. #define MOD (1000000007LL)
  7. #define LEFT(n) (2*(n))
  8. #define RIGHT(n) (2*(n)+1)
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef pair<ll, ll> ii;
  13. typedef pair<int, ii> iii;
  14.  
  15. ll pwr(ll base, ll p, ll mod=MOD){
  16. ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
  17. }
  18.  
  19.  
  20. ll gcd(ll a, ll b){
  21.     if(b == 0)  return a;
  22.     return gcd(b, a%b);
  23. }
  24.  
  25.  
  26.  
  27. int n, lps[100005], cnt[100005];
  28. string str;
  29.  
  30.  
  31. ll solve(string str){
  32.  
  33.     int n = (int)str.length();
  34.     lps[0] = cnt[0] = 0;
  35.     ll ans = 0;
  36.     for(int i=1;i<n;i++){
  37.         int j = lps[i-1];
  38.         while(j > 0 && str[j] != str[i])    j = lps[j-1];
  39.         if(str[j] == str[i])    j++;
  40.         lps[i] = j;
  41.         int period = (i+1) - lps[i];
  42.         if((i+1) % period == 0)
  43.             ans += (i+1)/period-1;
  44.     }
  45.  
  46. // for(int i=0;i<n;i++)    cout<<lps[i]<<" ";cout<<endl;
  47. // for(int i=0;i<n;i++)    cout<<cnt[i]<<" ";cout<<endl;
  48. // cout<<"solve "<<str<<" returns "<<ans<<endl;
  49.     return ans;
  50. }
  51.  
  52.  
  53. int main(){
  54.  
  55.     ios_base::sync_with_stdio(0);
  56.     cin.tie(0);
  57.  
  58.     cin>>str;
  59.     n = (int)str.length();
  60.  
  61.     ll ans = 0;
  62.     for(int i=0;i<n;i++){
  63.         ans += solve(str.substr(i));
  64.     }
  65.  
  66.     ans *= 2;
  67.     ans += 1LL*n*(n+1)/2;
  68.     cout<<ans;
  69.     return 0;
  70. }
  71.  
  72.  
Success #stdin #stdout 0s 16848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Duainf
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!