SHARE
TWEET

ыыыы2

a guest Oct 15th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cmath>
  6.  
  7. typedef long long ll;
  8.  
  9. const ll mod = 1e9 + 7;
  10. const int p = 247;
  11. std::vector<ll> pow_p = {1};
  12. int n;
  13.  
  14. void hash_func(std::vector<ll> &hash, std::string &s) {
  15.     hash.resize(n + 1, 0);
  16.     for (int i = 1; i < n + 1; i++) {
  17.         hash[i] = ((hash[i - 1] * p) % mod + s[i - 1]) % mod;
  18.     }
  19. }
  20.  
  21. ll get_hash(std::vector<ll> &hash, int l, int r) {
  22.     return (hash[r] - (hash[l - 1] * pow_p[r - l + 1]) % mod + mod) % mod;
  23. }
  24.  
  25. ll get_n_hash(std::vector<ll> &hash, int l, int r) {
  26.     return get_hash(hash, l, r);
  27. }
  28.  
  29. ll get_r_hash(std::vector<ll> &hash, int l, int r) {
  30.     return get_hash(hash, n - r + 1, n - l + 1);
  31. }
  32.  
  33. int main() {
  34. #ifdef LOCAL
  35.     freopen("input.txt", "r", stdin);
  36.     freopen("output.txt", "w", stdout);
  37. #endif
  38.     std::cin >> n;
  39.     std::string s;
  40.     std::cin >> s;
  41.     for (int i = 1; i < n + 1; i++)
  42.         pow_p.push_back((pow_p[i - 1] * p) % mod);
  43.     std::vector<ll> n_hash;
  44.     std::vector<ll> r_hash;
  45.     hash_func(n_hash, s);
  46.     std::reverse(s.begin(), s.end());
  47.     hash_func(r_hash, s);
  48.     bool flag = false;
  49.     for (int k = 0; k < n; k++) {
  50.         ll h = ((get_n_hash(n_hash, k + 1, n) * pow_p[k]) % mod + get_n_hash(n_hash, 1, k)) % mod;
  51.         if (h == get_r_hash(r_hash, 1, n)) {
  52.             std::cout << k;
  53.             return 0;
  54.         }
  55.     }
  56.     std::cout << -1;
  57.     return 0;
  58. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top