Advertisement
Guest User

Untitled

a guest
Aug 21st, 2017
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7.  
  8. const int maxn = 1e5 + 5;
  9.  
  10. ull h[2][maxn];
  11. ull deg[maxn];
  12.  
  13. const ull p = 409;
  14.  
  15. ull get_hash(int l, int r, int num)
  16. {
  17. assert(deg[r - l + 1] > 0);
  18. assert(r - l + 1 >= 0);
  19. return h[num][r + 1] - h[num][l] * deg[r - l + 1];
  20. }
  21.  
  22. int main()
  23. {
  24. char buf[maxn];
  25. scanf("%s", buf);
  26. string s1(buf);
  27. scanf("%s", buf);
  28. string s2(buf);
  29. string cycle_shifts = s2 + s2;
  30. int n = (int)s2.size();
  31. deg[0] = 1;
  32. assert((int)cycle_shifts.size() == 2 * n);
  33. for(int i = 0; i < (int)cycle_shifts.size(); i++)
  34. {
  35. h[0][i + 1] = h[0][i] * p + cycle_shifts[i];
  36. deg[i + 1] = deg[i] * p;
  37. }
  38. for(int i = 0; i < (int)s1.size(); i++)
  39. {
  40. h[1][i + 1] = h[1][i] * p + s1[i];
  41. }
  42. vector<ull>hashes(n);
  43. for(int i = 0; i < n; i++)
  44. {
  45. hashes[i] = get_hash(i, i + n - 1, 0);
  46. }
  47. assert((int)hashes.size() == n);
  48. sort(hashes.begin(), hashes.end());
  49. int ans = 0;
  50. for(int i = 0; i < (int)s1.size() - n + 1; i++)
  51. {
  52. assert(i + n - 1 < (int)s1.size());
  53. ull curHash = get_hash(i, i + n - 1, 1);
  54. if(binary_search(hashes.begin(), hashes.end(), curHash))
  55. ans++;
  56. }
  57. printf("%d", ans);
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement