Advertisement
MathQ_

Untitled

Mar 23rd, 2021
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. const ull mod = 1e9 + 289;
  2. const int p1 = 1000199, p2 = 1000289;
  3. vector<ull> deg1, deg2;
  4.  
  5. ull get_hash1(int l, int r, vector<ull> &h) {
  6.     return h[r] - h[l] * deg1[r - l];
  7. }
  8.  
  9. ull get_hash2(int l, int r, vector<ull> &h) {
  10.     return (h[r] + mod - h[l] * deg2[r - l] % mod) % mod;
  11. }
  12.  
  13. int main() {
  14.     fast
  15. //  file_in
  16. //  file_in_out
  17.  
  18.     int n, m;
  19.     cin >> n >> m;
  20.     vector<int> a(2 * n);
  21.     for (int i = 0; i < n; ++i) {
  22.         cin >> a[i];
  23.         a[2 * n - i - 1] = a[i];
  24.     }
  25.  
  26.     // считаем степени p
  27.     deg1.resize(2 * n + 1); deg2.resize(2 * n + 1);
  28.     deg1[0] = 1; deg2[0] = 1;
  29.     for (int i = 0; i < 2 * n; ++i) {
  30.         deg1[i + 1] = deg1[i] * p1;
  31.         deg2[i + 1] = (deg2[i] * p2) % mod;
  32.     }
  33.  
  34.     // считаем хеши
  35.     vector<ull> h1(2 * n + 1), h2(2 * n + 1);
  36.     h1[0] = 0; h2[0] = 0;
  37.     for (int i = 0; i < 2 * n; ++i) {
  38.         h1[i + 1] = h1[i] * p1 + a[i];
  39.         h2[i + 1] = (h2[i] * p2 % mod + a[i]) % mod;
  40.     }
  41.  
  42.     // сравниваем подстроки
  43.     vector<int> ans;
  44.     for (int i = 0; i <= n - i; ++i) {
  45.         if (h1[i] == get_hash1(2 * n - 2 * i, 2 * n - i, h1) && h2[i] == get_hash2(2 * n - 2 * i, 2 * n - i, h2)) {
  46.             ans.push_back(n - i);
  47.         }
  48.     }
  49.     for (int i = (int)ans.size() - 1; i >= 0; --i) {
  50.         cout << ans[i] << " ";
  51.     }
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement