daily pastebin goal
24%
SHARE
TWEET

Untitled

a guest Mar 21st, 2019 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#include <bits/stdc++.h>
  2. //#pragma GCC optimize("Ofast")
  3.  
  4. #include <vector>
  5. #include <algorithm>
  6. #include <iostream>
  7.  
  8. #define ll long long
  9. #define ld long double
  10. #define F first
  11. #define S second
  12. #define pb push_back
  13. #define mp make_pair
  14.  
  15. using namespace std;
  16.  
  17. const int maxn = 200005;
  18.  
  19. int p = 67;
  20. int m = 1e9 + 87;
  21. int h[maxn];
  22. int st[maxn];
  23.  
  24. void hsh(string& s)
  25. {
  26.     h[0] = int(s[0]) - int('0') + 1;
  27.     for(int i = 1; i < int(s.size()); i++)
  28.     {
  29.         h[i] = ((1ll * h[i - 1] * p) % m + int(s[i]) - int('0') + 1) % m;
  30.     }
  31.     return;
  32. }
  33.  
  34. int gethash(int l, int r)
  35. {
  36.     int ans = h[r];
  37.     if (l > 0) ans -= (1ll * h[l - 1] * st[r - l + 1]) % m;
  38.     ans += m;
  39.     ans %= m;
  40.     return ans;
  41. }
  42.  
  43. int main()
  44. {
  45. #ifdef LOCAL
  46.     freopen("input.txt", "r", stdin);
  47.     freopen("output.txt", "w", stdout);
  48. #else
  49.     freopen("robot.in", "r", stdin);
  50.     freopen("robot.out", "w", stdout);
  51. #endif
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(0);
  54.     cout.tie(0);
  55.     st[0] = 1;
  56.     for(int i = 1; i < maxn; i++)
  57.         st[i] = (1ll * st[i - 1]) % m;
  58.     int k;
  59.     string s;
  60.     cin >> k >> s;
  61.     hsh(s);
  62.     ll ans = 0;
  63.     for(int i = 0; i + k - 1 < int(s.size()); i++)
  64.     {
  65.         int n = i;
  66.         int H = gethash(n, n + k - 1);
  67.         int c = 0;
  68.         for(int j = n + k; ; j += k)
  69.         {
  70.             if (j + k - 1 >= int(s.size())) break;
  71.             if (H == gethash(j, j + k - 1)) c++;
  72.                 else break;
  73.             i += k;
  74.         }
  75.         ll t = (c * k);
  76.         for(int j = n + k * (c + 1); j < int(s.size()); j++)
  77.             if (s[n] == s[j]) {t++; i++; n++;}
  78.                 else break;
  79.         ans += (t * (t + 1)) / 2;
  80.  
  81.     }
  82.     cout << ans;
  83.     return 0;
  84. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top