Salvens

E

Aug 9th, 2023
790
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.90 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 = 1e6 + 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.  
  24. array<int, MAXN> power1, power2;
  25.  
  26. inline void init_pow() {
  27.     power1[0] = 1;
  28.     power2[0] = 1;
  29.     for (int i = 1; i < MAXN; ++i) {
  30.         power1[i] = (1ll * power1[i - 1] * P1) % M1;
  31.         power2[i] = (1ll * power2[i - 1] * P2) % M2;
  32.     }
  33. }
  34.  
  35. inline void build_hash(string& s, vector<pair<int, int>>& h) {
  36.     int n = s.size();
  37.     h.resize(n + 1);
  38.     h[0].first = 0;
  39.     h[0].second = 0;
  40.  
  41.     for (int i = 0; i < n; ++i) {
  42.         h[i + 1].first = (h[i].first + 1ll * s[i] * power1[i]) % M1;
  43.         h[i + 1].second = (h[i].second + 1ll * s[i] * power2[i]) % M2;
  44.     }
  45. }
  46.  
  47. inline bool is_equal(vector<pair<int, int>>& h_l, vector<pair<int, int>>& h_r, int start1, int start2, int len) {
  48.     pair<int, int> d_l, d_r;
  49.     d_l.first = ((h_l[start1 + len].first - h_l[start1].first + M1) % M1 * 1ll * power1[start2]) % M1;
  50.     d_l.second = ((h_l[start1 + len].second - h_l[start1].second + M2) % M2 * 1ll * power2[start2]) % M2;
  51.  
  52.     d_r.first = ((h_r[start2 + len].first - h_r[start2].first + M1) % M1 * 1ll * power1[start1]) % M1;
  53.     d_r.second = ((h_r[start2 + len].second - h_r[start2].second + M2) % M2 * 1ll * power2[start1]) % M2;
  54.  
  55.     return d_l == d_r;
  56. }
  57.  
  58. inline int random_key(const int before, const int after) {
  59.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  60.     std::mt19937 mt_rand(seed);
  61.     int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
  62.     return base;
  63. }
  64.  
  65. signed main() {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(nullptr);
  68.     cout.tie(nullptr);
  69.  
  70.     P1 = random_key(256, M1);
  71.     P2 = random_key(256, M2);
  72.  
  73.     string a, b;
  74.     cin >> a;
  75.     int n = a.size();
  76.     b = a;
  77.     reverse(b.begin(), b.end());
  78.  
  79.     vector<pair<int, int>> h_a, h_b;
  80.     init_pow();
  81.     build_hash(a, h_a);
  82.     build_hash(b, h_b);
  83.  
  84.     long long ans = 0;
  85.  
  86.     for (int i = 0, j = n - 1; i < n; ++i, --j) {
  87.         int l = 0, r = min(n - i, n - j) + 1;
  88.         while (r - l > 1) {
  89.             int mid = (r + l) / 2;
  90.             if (is_equal(h_a, h_b, i, j, mid)) {
  91.                 l = mid;
  92.             } else {
  93.                 r = mid;
  94.             }
  95.         }
  96.         ans += l;
  97.  
  98.         l = 0, r = min(n - i - 1, n - j) + 1;
  99.         while (r - l > 1) {
  100.             int mid = (r + l) / 2;
  101.             if (is_equal(h_a, h_b, i + 1, j, mid)) {
  102.                 l = mid;
  103.             } else {
  104.                 r = mid;
  105.             }
  106.         }
  107.         ans += l;
  108.     }
  109.     cout << ans << '\n';
  110. }
Advertisement
Add Comment
Please, Sign In to add comment