Advertisement
Guest User

Untitled

a guest
Jul 17th, 2022
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define isz(x) (int)(x).size()
  3. #define all(x) (x).begin(),(x).end()
  4.  
  5. using ull = uint64_t;
  6. using hash = std::pair<int,ull>;
  7.  
  8. const int mod = 2000000011;
  9.  
  10. const int NMAX = 2020;
  11.  
  12. hash operator*(hash a, hash b) {
  13.     return {a.first * 1LL * b.first % mod, a.second * b.second};
  14. }
  15.  
  16. hash operator+(hash a, hash b) {
  17.     return {(0LL + a.first + b.first) % mod, a.second + b.second};
  18. }
  19.  
  20. hash operator-(hash a, hash b) {
  21.     return {(0LL + a.first - b.first + mod) % mod, a.second - b.second};
  22. }
  23.  
  24. const std::vector<hash> power = [](){
  25.     std::mt19937 gen(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  26.     int p = std::uniform_int_distribution<int>(mod/2,mod-2)(gen);
  27.     if (p % 2 == 0) p++;
  28.     std::vector<hash> answer(NMAX,{1,1});
  29.     for (int i = 1; i < NMAX; i++) {
  30.         answer[i] = answer[i-1] * hash(p,p);
  31.     }
  32.     return answer;
  33. }();
  34.  
  35. struct Hash {
  36.     std::vector<hash> pref;
  37.    
  38.     Hash(const std::string &s) {
  39.         // создать структуру
  40.         pref.assign(isz(s)+1,{0,0});
  41.         for (int i = 0; i < isz(s); i++) {
  42.             pref[i+1] = pref[i] * power[1] + hash(s[i],s[i]);
  43.         }
  44.     }
  45.    
  46.     hash getHash(int i, int j) const {
  47.         if (i > j) return {0, 0};
  48.         // считаем хэш на отрезке
  49.         return pref[j+1] - pref[i] * power[j-i+1];
  50.     }
  51. };
  52.  
  53. main() {
  54.     std::ios::sync_with_stdio(false);
  55.     std::cin.tie(0);
  56.     freopen("bacon.in", "rt", stdin);
  57.     freopen("bacon.out", "wt", stdout);
  58.     std::string s; std::cin >> s;
  59.     Hash h(s);
  60.     std::vector<hash> hashes;
  61.     for (int i = 0; i < isz(s); i++)
  62.         for (int j = i; j < isz(s); j++)
  63.             hashes.push_back( h.getHash(i,j) );
  64.     std::sort(all(hashes));
  65.     std::cout << std::unique(all(hashes)) - hashes.begin() << std::endl;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement