Advertisement
Guest User

Untitled

a guest
Aug 18th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. const int64_t P = 2017;
  8. const int64_t MOD = 1000000007;
  9. const int MAX = 100100;
  10.  
  11. int64_t powers[MAX];
  12. int64_t pref[MAX];
  13. int64_t rpref[MAX];
  14.  
  15. void precalc_powers(int64_t *p, int64_t base, int64_t mod)
  16. {
  17. p[0] = 1;
  18. for (int i = 1; i < MAX; ++i)
  19. {
  20. p[i] = p[i - 1] * base % mod;
  21. }
  22. }
  23.  
  24. void precalc_hash(int64_t *a, string &line, int64_t base, int64_t mod)
  25. {
  26. a[0] = 0;
  27. for (int i = 1; i <= line.size(); ++i)
  28. {
  29. a[i] = (a[i - 1] * base + (signed char)line[i - 1]) % mod;
  30. }
  31. }
  32.  
  33. int64_t get_hash(int l, int r, int64_t *a, int64_t *pows, int64_t mod)
  34. {
  35. return (a[r] - a[l] * pows[r - l] % mod + mod) % mod;
  36. }
  37.  
  38. int main()
  39. {
  40. string line;
  41. cin >> line;
  42. string rline = line;
  43. reverse(rline.begin(), rline.end());
  44. precalc_powers(powers, P, MOD);
  45. precalc_hash(pref, line, P, MOD);
  46. precalc_hash(rpref, rline, P, MOD);
  47. int64_t odd_max = -1;
  48.  
  49.  
  50. return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement