fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #define ll long long
  4. bool yes = 0;
  5. #define fr(i, a, b) for(int i = a; i <= b; i++)
  6. #define frd(i, a, b) for(int i = a; i >= b; i--)
  7. #define pb push_back
  8. #define pu push
  9. #define name
  10. #define oo 1e9
  11. #define pii pair<int, int>
  12. #define pll pair<ll, ll>
  13. #define fi first
  14. #define se second
  15. #define tangtoc ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  16. #define BIT(x,i) (((x) >> (i)) & 1)
  17. #define MASK(i) ((1LL) << (i))
  18. #define sz(s) (int)(s.size())
  19. using namespace std;
  20. using namespace __gnu_pbds;
  21. const int N = 5*1e6,sm = 1e9+7,M = 2*1e5+20,BIT = 25;
  22. template <class X, class Y>
  23.     bool maximize(X &x, const Y &y){
  24.         if (x < y){
  25.             x = y;
  26.             return true;
  27.         }
  28.         return false;
  29.     }
  30. template <class X, class Y>
  31.     bool minimize(X &x, const Y &y){
  32.         if (x > y){
  33.             x = y;
  34.             return true;
  35.         }
  36.         return false;
  37.     }
  38. ll add(ll x,const ll &y){
  39.     x = (x%sm+y)%sm;
  40.     return x;
  41. }
  42. ll mul(ll x,const ll &y){
  43.     x = (x%sm*y)%sm;
  44.     return x;
  45. }
  46. ll modpow(ll a,ll b,ll sm){
  47.     ll res = 1;
  48.     a %= sm;
  49.     while (b){
  50.         if (b & 1) res = res*a%sm;
  51.         a = a*a%sm;
  52.         b >>= 1;
  53.     }
  54.     return res;
  55. }
  56. /*struct pair_hash {
  57.     std::size_t operator()(const std::pair<int, int>& p) const {
  58.         return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1);
  59.     }
  60. };
  61. gp_hash_table<ll,ll> mp;
  62. */
  63. //------------------------------------------------------NEVER-ENOUGH--------------------------------------------------------------
  64. int n,kmp[N];
  65. string s;
  66. void read(){
  67.     cin >> s;
  68.     n = sz(s);
  69.     s = "_"+s;
  70. }
  71. void solve(){
  72.     int k = kmp[1] = 0;
  73.     for (int i = 2; i <= n; i++){
  74.         while (k > 0 && s[i] != s[k+1]) k = kmp[k];
  75.         kmp[i] = (s[i] == s[k+1]) ? ++k : 0;
  76.     }
  77.     multiset <int> se;
  78.     ll res = 0;
  79.     for (int i = 1; i <= n; i++){
  80.         int tmp = kmp[i];
  81.         if (se.count(tmp)) res += tmp;
  82.         else res += kmp[kmp[i]];
  83.         se.insert(tmp);
  84.     }
  85.     cout << res;
  86. }
  87. int main(){
  88.     tangtoc;
  89.     //Code bat dau tu day
  90.     //freopen("name.INP","r",stdin);
  91.     //freopen("name.OUT","w",stdout);
  92.     int test; test = 1;
  93.     if (yes) cin >> test;
  94.     for (int i = 1; i <= test; i++){
  95.         read();
  96.         solve();
  97.     }
  98.     cerr << "\nTime : " << 0.001 * clock() << "s ";
  99.     return 0;
  100. }
  101. //-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  102.  
  103.  
  104.  
Success #stdin #stdout #stderr 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time : 6.341s
https://ideone.com/xqCZSd
language:
C++14 (gcc 8.3)
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!