Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define isz(x) (int)(x).size()
- #define all(x) (x).begin(),(x).end()
- using ull = uint64_t;
- using hash = std::pair<int,ull>;
- const int mod = 2000000011;
- const int NMAX = 2020;
- hash operator*(hash a, hash b) {
- return {a.first * 1LL * b.first % mod, a.second * b.second};
- }
- hash operator+(hash a, hash b) {
- return {(0LL + a.first + b.first) % mod, a.second + b.second};
- }
- hash operator-(hash a, hash b) {
- return {(0LL + a.first - b.first + mod) % mod, a.second - b.second};
- }
- const std::vector<hash> power = [](){
- std::mt19937 gen(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- int p = std::uniform_int_distribution<int>(mod/2,mod-2)(gen);
- if (p % 2 == 0) p++;
- std::vector<hash> answer(NMAX,{1,1});
- for (int i = 1; i < NMAX; i++) {
- answer[i] = answer[i-1] * hash(p,p);
- }
- return answer;
- }();
- struct Hash {
- std::vector<hash> pref;
- Hash(const std::string &s) {
- // создать структуру
- pref.assign(isz(s)+1,{0,0});
- for (int i = 0; i < isz(s); i++) {
- pref[i+1] = pref[i] * power[1] + hash(s[i],s[i]);
- }
- }
- hash getHash(int i, int j) const {
- if (i > j) return {0, 0};
- // считаем хэш на отрезке
- return pref[j+1] - pref[i] * power[j-i+1];
- }
- };
- main() {
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- freopen("bacon.in", "rt", stdin);
- freopen("bacon.out", "wt", stdout);
- std::string s; std::cin >> s;
- Hash h(s);
- std::vector<hash> hashes;
- for (int i = 0; i < isz(s); i++)
- for (int j = i; j < isz(s); j++)
- hashes.push_back( h.getHash(i,j) );
- std::sort(all(hashes));
- std::cout << std::unique(all(hashes)) - hashes.begin() << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement