Advertisement
Guest User

Untitled

a guest
Aug 20th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <math.h>
  4. #include <vector>
  5. #include <set>
  6. #include <unordered_set>
  7. #include <tuple>
  8. #include <map>
  9. #include <unordered_map>
  10. #include <string>
  11. #include <string.h>
  12. #include <utility>
  13. #include <algorithm>
  14. #include <queue>
  15. #include <deque>
  16. #include <iterator>
  17. #include <stdlib.h>
  18. #include <cstdlib>
  19. #include <bitset>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24.  
  25. inline ll subhash(vector<ll>& hash, ll l, ll r, ll mod, vector<ll>& pw) {
  26. ll big = hash[r];
  27. ll small = 0;
  28. if (l != 0) {
  29. small = (hash[l - 1] * pw[r - l + 1]) % mod;
  30. }
  31. return (big - small + mod) % mod;
  32. }
  33.  
  34. int main() {
  35. const ll mod = 2e9 + 63;
  36. const ll p = 173;
  37. string entry; cin >> entry;
  38. string dima; cin >> dima;
  39. entry += entry;
  40. ll kol = entry.size();
  41. ll dimKol = dima.size();
  42. vector <ll> hash(kol);
  43. vector<ll> dimHash(dimKol);
  44. vector <ll> pw(50000);
  45.  
  46. hash[0] = entry[0];
  47. for (int i = 1; i < kol; ++i) {
  48. hash[i] = ((hash[i - 1] * p) + entry[i]) % mod;
  49. }
  50.  
  51. dimHash[0] = dima[0];
  52. for (int i = 1; i < kol; ++i) {
  53. dimHash[i] = ((dimHash[i - 1] * p) + dima[i]) % mod;
  54. }
  55.  
  56. pw[0] = 1;
  57. for (int i = 1; i < 50000; ++i) {
  58. pw[i] = (pw[i - 1] * p) % mod;
  59. }
  60.  
  61. ll dimHashAns = dimHash[dimKol - 1];
  62.  
  63. for (int i = 1; i < dimKol + 1; ++i) {
  64. ll ans = subhash(hash, i, i + dimKol - 1, mod, pw);
  65. cout << ans << " " << dimHashAns << endl;
  66. if (dimHashAns == ans) {
  67. cout << i;
  68. exit(0);
  69. }
  70. }
  71.  
  72. cout << -1;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement