Salvens

G

Aug 11th, 2023
884
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.29 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8.  
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #pragma comment(linker,"/STACK:1000000000,1000000000")
  14.  
  15. const long long INF = 1e9 + 7;
  16. const int MAXN = 2e5 + 1000;
  17. const int N = 1e5 + 10;
  18.  
  19. const int M1 = 1e9 + 123;
  20. const int M2 = 1e9 + 321;
  21. int P1 = 22811;
  22. int P2 = 22699;
  23. array<int, MAXN> power1, power2;
  24.  
  25. void init_pow() {
  26.     power1[0] = 1;
  27.     power2[0] = 1;
  28.     for (int i = 1; i < MAXN; ++i) {
  29.         power1[i] = (power1[i - 1] * P1) % M1;
  30.         power2[i] = (power2[i - 1] * P2) % M2;
  31.     }
  32. }
  33.  
  34. void build_hash(string& s, vector<pair<int, int>>& h) {
  35.     int n = s.size();
  36.     h.resize(n + 1);
  37.     h[0].first = 0;
  38.     h[0].second = 0;
  39.  
  40.     for (int i = 0; i < n; ++i) {
  41.         h[i + 1].first = (h[i].first + s[i] * power1[i]) % M1;
  42.         h[i + 1].second = (h[i].second + s[i] * power2[i]) % M2;
  43.     }
  44. }
  45.  
  46. pair<int, int> get_hash(vector<pair<int, int>>& h, int pos, int len, int mx_pow = 0) {
  47.     int h1 = h[pos + len].first - h[pos].first;
  48.     int h2 = h[pos + len].second - h[pos].second;
  49.     if (h1 < 0) {
  50.         h1 += M1;
  51.     }
  52.     if (h2 < 0) {
  53.         h2 += M2;
  54.     }
  55.     if (mx_pow != 0) {
  56.         h1 = h1 * power1[mx_pow - (pos + len - 1)] % M1;
  57.         h2 = h2 * power2[mx_pow - (pos + len - 1)] % M2;
  58.     }
  59.     return make_pair(h1, h2);
  60. }
  61.  
  62. bool is_equal(vector<pair<int, int>>& h_l, vector<pair<int, int>>& h_r, int start1, int start2, int len) {
  63.     pair<int, int> d_l, d_r;
  64.     d_l.first = ((h_l[start1 + len].first - h_l[start1].first + M1) % M1 * power1[start2]) % M1;
  65.     d_l.second = ((h_l[start1 + len].second - h_l[start1].second + M2) % M2 * power2[start2]) % M2;
  66.  
  67.     d_r.first = ((h_r[start2 + len].first - h_r[start2].first + M1) % M1 * power1[start1]) % M1;
  68.     d_r.second = ((h_r[start2 + len].second - h_r[start2].second + M2) % M2 * power2[start1]) % M2;
  69.  
  70.     return d_l == d_r;
  71. }
  72.  
  73. int random_key(const int before, const int after) {
  74.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  75.     std::mt19937 mt_rand(seed);
  76.     int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
  77.     return base;
  78. }
  79.  
  80. int sum(int a, int k, int mod) {
  81.     if (k == 1) {
  82.         return 1;
  83.     } else if (k % 2 == 0) {
  84.         return (1ll + a) * sum(1ll * a * a % mod, k / 2, mod) % mod;
  85.     } else {
  86.         return 1 + (a + 1ll) * a % mod * sum(1ll * a * a % mod, k / 2, mod) % mod;
  87.     };
  88. }
  89.  
  90. signed main() {
  91.     ios_base::sync_with_stdio(false);
  92.     cin.tie(nullptr);
  93.     cout.tie(nullptr);
  94.  
  95.     P1 = random_key(256, M1);
  96.     P2 = random_key(256, M2);
  97.  
  98.     string a;
  99.     cin >> a;
  100.     int n = a.size();
  101.     reverse(a.begin(), a.end());
  102.  
  103.  
  104.     vector<pair<int, int>> h_a;
  105.     init_pow();
  106.     build_hash(a, h_a);
  107.  
  108.     int ans = 0;
  109.     for (int len = 1; len <= n; ++len) {
  110.         auto h1 = h_a[len];
  111.         auto h2 = h_a[n];
  112.  
  113.         h1.first = 1ll * h1.first * sum(power1[len], n, M1) % M1;
  114.         h2.first = 1ll * h2.first * sum(power1[n], len, M1) % M1;
  115.  
  116.         h1.second = 1ll * h1.second * sum(power2[len], n, M2) % M2;
  117.         h2.second = 1ll * h2.second * sum(power2[n], len, M2) % M2;
  118.  
  119.         ans += (h1 == h2);
  120.     }
  121.     cout << ans << '\n';
  122. }
Advertisement
Add Comment
Please, Sign In to add comment