Guest User

Untitled

a guest
Jan 11th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define D 50007
  4. #define step 67
  5.  
  6. using namespace std;
  7. typedef unsigned long long ull;
  8. typedef ull arr[D];
  9.  
  10. string s1, s2, s1rev;
  11. ull p[D], h1[D], h2[D], h1rev[D];
  12.  
  13. ull get_hash(ull l, ull r, arr &h)
  14. {
  15. return h1[r] - h1[l-1];
  16. }
  17.  
  18. int main()
  19. {
  20. cin >> s1 >> s2;
  21.  
  22. if (s1.size() != s2.size())
  23. return cout << "No" << endl, 0;
  24. for (ull i = 0; i < s1.size(); i++)
  25. {
  26. s1[i] -= 60;
  27. s2[i] -= 60;
  28. }
  29.  
  30. s1rev = s1;
  31. reverse(s1rev.begin(), s1rev.end());
  32.  
  33. ull n = s1.size();
  34. s1 = ' ' + s1;
  35. s2 = ' ' + s2;
  36. s1rev = ' ' + s1rev;
  37.  
  38. p[0] = 1;
  39. for (ull i = 1; i <= n + 1; i++)
  40. p[i] = p[i - 1] * step;
  41. for (ull i = 1; i <= n; i++)
  42. {
  43. h1[i] = h1[i - 1]*step + s1[i];
  44. h2[i] = h2[i - 1]*step + s2[i];
  45. h1rev[i] = h1rev[i]*step + s1rev[i];
  46. }
  47.  
  48. for (ull i = 0; i <= n; i++)
  49. {
  50. ull hash1 = get_hash(i, n, h1) + get_hash(n-i-1, n, h1rev)*p[i+1];
  51. ull hash2 = h2[n]*p[i+1];
  52. if (hash1 == hash2)
  53. return cout << "Yes" << " " << i << endl, 0;
  54. }
  55. cout << "No" << endl;
  56. return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment