Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <array>
- #include <vector>
- #include <numeric>
- #include <random>
- #include <chrono>
- using namespace std;
- #define int long long
- #pragma comment(linker,"/STACK:1000000000,1000000000")
- const long long INF = 1e9 + 7;
- const int MAXN = 2e5 + 1000;
- const int N = 1e5 + 10;
- const int M1 = 1e9 + 123;
- const int M2 = 1e9 + 321;
- int P1 = 22811;
- int P2 = 22699;
- array<int, MAXN> power1, power2;
- void init_pow() {
- power1[0] = 1;
- power2[0] = 1;
- for (int i = 1; i < MAXN; ++i) {
- power1[i] = (power1[i - 1] * P1) % M1;
- power2[i] = (power2[i - 1] * P2) % M2;
- }
- }
- void build_hash(string& s, vector<pair<int, int>>& h) {
- int n = s.size();
- h.resize(n + 1);
- h[0].first = 0;
- h[0].second = 0;
- for (int i = 0; i < n; ++i) {
- h[i + 1].first = (h[i].first + s[i] * power1[i]) % M1;
- h[i + 1].second = (h[i].second + s[i] * power2[i]) % M2;
- }
- }
- pair<int, int> get_hash(vector<pair<int, int>>& h, int pos, int len, int mx_pow = 0) {
- int h1 = h[pos + len].first - h[pos].first;
- int h2 = h[pos + len].second - h[pos].second;
- if (h1 < 0) {
- h1 += M1;
- }
- if (h2 < 0) {
- h2 += M2;
- }
- if (mx_pow != 0) {
- h1 = h1 * power1[mx_pow - (pos + len - 1)] % M1;
- h2 = h2 * power2[mx_pow - (pos + len - 1)] % M2;
- }
- return make_pair(h1, h2);
- }
- bool is_equal(vector<pair<int, int>>& h_l, vector<pair<int, int>>& h_r, int start1, int start2, int len) {
- pair<int, int> d_l, d_r;
- d_l.first = ((h_l[start1 + len].first - h_l[start1].first + M1) % M1 * power1[start2]) % M1;
- d_l.second = ((h_l[start1 + len].second - h_l[start1].second + M2) % M2 * power2[start2]) % M2;
- d_r.first = ((h_r[start2 + len].first - h_r[start2].first + M1) % M1 * power1[start1]) % M1;
- d_r.second = ((h_r[start2 + len].second - h_r[start2].second + M2) % M2 * power2[start1]) % M2;
- return d_l == d_r;
- }
- int random_key(const int before, const int after) {
- auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
- std::mt19937 mt_rand(seed);
- int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
- return base;
- }
- int sum(int a, int k, int mod) {
- if (k == 1) {
- return 1;
- } else if (k % 2 == 0) {
- return (1ll + a) * sum(1ll * a * a % mod, k / 2, mod) % mod;
- } else {
- return 1 + (a + 1ll) * a % mod * sum(1ll * a * a % mod, k / 2, mod) % mod;
- };
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- P1 = random_key(256, M1);
- P2 = random_key(256, M2);
- string a;
- cin >> a;
- int n = a.size();
- reverse(a.begin(), a.end());
- vector<pair<int, int>> h_a;
- init_pow();
- build_hash(a, h_a);
- int ans = 0;
- for (int len = 1; len <= n; ++len) {
- auto h1 = h_a[len];
- auto h2 = h_a[n];
- h1.first = 1ll * h1.first * sum(power1[len], n, M1) % M1;
- h2.first = 1ll * h2.first * sum(power1[n], len, M1) % M1;
- h1.second = 1ll * h1.second * sum(power2[len], n, M2) % M2;
- h2.second = 1ll * h2.second * sum(power2[n], len, M2) % M2;
- ans += (h1 == h2);
- }
- cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment