Advertisement
drof13

Untitled

Mar 5th, 2022
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <stack>
  11. #include <deque>
  12. #include <queue>
  13. #include <climits>
  14.  
  15.  
  16. #define int long long
  17. #define db double
  18. #define ff first
  19. #define ss second
  20.  
  21. using namespace std;
  22.  
  23. const int MOD = 1e9 + 7;
  24. // const int INF = LONG_MAX;
  25. const int INF = INT_MAX;
  26. const int K = 31;
  27.  
  28. int hash_substring(vector<int>& h, vector<int>& k, int l, int r, int n) {
  29.     return (h[r] - h[l]) * k[n - l] % MOD;
  30. }
  31.  
  32. signed main() {
  33.     ios_base::sync_with_stdio(0);
  34.     cin.tie(0);
  35.     cout.tie(0);
  36.     string s;
  37.     cin >> s;
  38.     vector<int> hash1(s.size());
  39.     vector<int> hash2(s.size());
  40.     vector<int> k(s.size() + 1);
  41.     k[0] = 1;
  42.     for (int i = 1; i < s.size() + 1; i++) {
  43.         k[i] = k[0] * K;
  44.     }
  45.     int h = 0;
  46.     for (int i = 0; i < s.size(); i++) {
  47.         int x = s[i] - 'a' + 1;
  48.         h = (h * K + x) % MOD;
  49.         hash1[i] = h;
  50.     }
  51.     h = 0;
  52.     for (int i = s.size() - 1; i >= 0; i--) {
  53.         int x = s[i] - 'a' + 1;
  54.         h = (h * K + x) % MOD;
  55.         hash2[s.size() - 1 - i] = h;
  56.     }
  57.     int h1 = 0, h2 = 0;
  58.     int l = 0, r = 1;
  59.     h1 = hash_substring(hash1, k, l, r, s.size());
  60.     h2 = hash_substring(hash2, k, s.size() - 1 - r, s.size() - 1 - l, s.size());
  61.     if (h1 == h2) {
  62.         cout << "YES";
  63.     }
  64.     else {
  65.         cout << "NO";
  66.     }
  67. }
  68. // a              ka + a   k^2a + ka + a
  69. // k^2a + ka + a  ka + a   a
  70.  
  71. // aaa
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement