Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2018
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.48 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int p = 239;
  9.  
  10. vector<unsigned long long> p_pow;
  11.  
  12. void getP(int n) {
  13. p_pow.push_back(1);
  14. for (int i = 0; i < n; ++i) {
  15. p_pow.push_back(p_pow[i] * p);
  16. }
  17. }
  18.  
  19. void hasher(string s, vector<unsigned long long> & hash) {
  20. hash.push_back(0);
  21. for (int i = 0; i < s.size(); ++i) {
  22. hash.push_back(hash[i] * p + s[i]);
  23. }
  24. }
  25.  
  26. void suf_hasher(string s, vector<unsigned long long> & hash) {
  27. reverse(s.begin(), s.end());
  28. hash.push_back(0);
  29. for (int i = 0; i < s.size(); ++i) {
  30. hash.push_back(hash[i] * p + s[i]);
  31. }
  32. }
  33.  
  34. int main() {
  35. getP(50000);
  36. string s1, s2;
  37. cin >> s1 >> s2;
  38. vector<unsigned long long> hash1, hash2, suf_hash1;
  39. hasher(s1, hash1);
  40. suf_hasher(s1, suf_hash1);
  41. hasher(s2, hash2);
  42. unsigned long long match = hash2[s2.size()] - hash2[0] * p_pow[s2.size()];
  43. int ans = -1;
  44. for (int i = 0; i < s1.size(); ++i) {
  45. unsigned long long h1 = hash1[s1.size()] - hash1[i] * p_pow[s1.size() - i];
  46. h1 *= p_pow[i];
  47. unsigned long long h2 = suf_hash1[s1.size()] - suf_hash1[s1.size() - i] * p_pow[i];
  48. if (h1 + h2 == match) {
  49. ans = s1.size() - i;
  50. break;
  51. }
  52. }
  53. if (ans == -1) {
  54. printf("No");
  55. return 0;
  56. }
  57. printf("Yes\n");
  58. printf("%d", s1.size() - ans);
  59. return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement