SHARE
TWEET

Untitled

a guest Feb 21st, 2020 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int BASE = 89;
  9. const uint32_t MOD = (uint32_t) 1e9 + 7;
  10.  
  11. uint32_t add(uint32_t a, uint32_t b) {
  12.     return (a + b) % MOD;
  13. }
  14.  
  15. uint32_t sub(uint32_t a, uint32_t b) {
  16.     return ((a - b) + MOD) % MOD;
  17. }
  18.  
  19. uint32_t mul(uint32_t a, uint32_t b) {
  20.     return ((long long)a * (long long)b) % MOD;
  21. }
  22.  
  23. vector<uint32_t> get_straight_hash_codes(string &s, vector<uint32_t> pows) {
  24.     vector<uint32_t> h;
  25.     h.resize(s.size());
  26.     h[0] = s[0];
  27.     for (int i = 1; i < s.size(); ++i) {
  28.         h[i] = add(h[i - 1],
  29.                    mul(s[i], pows[i]));
  30.     }
  31.     return h;
  32. }
  33.  
  34. vector<uint32_t> get_reverse_hash_codes(string &s, vector<uint32_t> pows) {
  35.     vector<uint32_t> h;
  36.     h.resize(s.size());
  37.     h[s.size() - 1] = s[s.size() - 1];
  38.     for (int i = s.size() - 2; i >= 0; --i) {
  39.         h[i] = add(h[i + 1],
  40.                    mul(s[i], pows[s.size() - 1 - i]));
  41.     }
  42.     return h;
  43. }
  44.  
  45. vector<uint32_t> get_pows(int sz) {
  46.     vector<uint32_t> pows;
  47.     pows.resize(sz);
  48.     pows[0] = 1;
  49.     for (int i = 1; i < sz; ++i) {
  50.         pows[i] = mul(pows[i-1], BASE);
  51.     }
  52.     return pows;
  53. }
  54.  
  55. void find_palindromes(string &s, int *res, int sz) {
  56.     vector<uint32_t> pows = get_pows(sz);
  57.     vector<uint32_t> sh = get_straight_hash_codes(s, pows);
  58.     vector<uint32_t> rh = get_reverse_hash_codes(s, pows);
  59.     for (int i = 0; i < sz; ++i) {
  60.         int max_len = min(i, sz - i - 1) + 1;
  61.         int min_len = 0;
  62.         while (min_len != max_len - 1) {
  63.             int len = (max_len + min_len) / 2;
  64.  
  65.             uint32_t l = sub(sh[i], (i - len <= 0) ? 0 : sh[i - len - 1]);
  66.             uint32_t r = sub(rh[i], (i + len >= sz - 1) ? 0 : rh[i + len + 1]);
  67.  
  68.             int p1 = i - len;
  69.             int p2 = sz - 1 - i - len;
  70.             if (p1 < p2) {
  71.                 l = mul(l, pows[p2 - p1]);
  72.             } else {
  73.                 r = mul(r, pows[p1 - p2]);
  74.             }
  75.  
  76.             if (l == r) {
  77.                 min_len = len;
  78.             } else {
  79.                 max_len = len;
  80.             }
  81.         }
  82.  
  83.         res[i] = 2 * min_len + 1;
  84.     }
  85. }
  86.  
  87. int main() {
  88.     string s;
  89.     cin >> s;
  90.     transform(begin(s), end(s), begin(s), ::tolower);
  91.     int sz = s.size();
  92.     int *res = new int[sz];
  93.     find_palindromes(s, res, sz);
  94.     for (int i = 0; i < sz; ++i) {
  95.         cout << res[i] << " ";
  96.     }
  97.     return 0;
  98. }
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
Top