Advertisement
Guest User

Untitled

a guest
Jan 16th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4. #define double long double
  5. #define For(i,z) for(int i=0;i<z;i++)
  6. #define ex(a) {cout << a; exit(0);}
  7.  
  8. using namespace std;
  9.  
  10. const int N = 5e3+5;
  11. const int INF = 1e12;
  12. const double PI = 3.1415926535897932384626433832795;
  13. const int MOD = 1e9+9;
  14.  
  15. int need;
  16. int n;
  17.  
  18. int hs[N];
  19. int rev[N];
  20. int mult[N];
  21.  
  22. string fr, to;
  23.  
  24. bool check(int k)
  25. {
  26.     int lef = (hs[n-1] - hs[k-1] + MOD) % MOD;        // : mult[k]
  27.     int rig = (rev[n-1] - rev[n-1-k] + MOD) % MOD;
  28.  
  29.     int cur = (lef + rig * mult[k]) % MOD;
  30.     int sec = need * mult[k] % MOD;
  31.  
  32.     //cout << k << " : " << cur << ' ' << sec << endl;
  33.  
  34.     return (cur == sec);
  35. }
  36.  
  37. int32_t main()
  38. {
  39.     ios_base::sync_with_stdio(0);
  40.  
  41.  
  42.     mult[0] = 1;
  43.     For (i, N-1) mult[i+1] = mult[i] * 101 % MOD;
  44.  
  45.     cin >> fr >> to;
  46.  
  47.     if (fr.size() != to.size()) ex("No\n")
  48.     if (to == fr) ex("Yes\n0")
  49.  
  50.     hs[0] = fr[0] - 'A'+1;
  51.     n = fr.size();
  52.     For (i, n-1) hs[i+1] = (hs[i] + (fr[i+1]-'A'+1)*mult[i+1]) % MOD;
  53.  
  54.     For (i, n) need += (to[i]-'A'+1)*mult[i], need %= MOD;
  55.  
  56.     rev[0] = fr[n-1]-'A'+1;
  57.     For (i, n-1)
  58.         rev[i+1] = (rev[i] + (fr[n-i-2] - 'A' + 1) * mult[i+1]) % MOD;
  59.  
  60.     For (i, n-1)
  61.         if (check(i+1))
  62.         {
  63.             cout << "Yes\n" << i+1 << endl;
  64.             return 0;
  65.         }
  66.     ex("No\n")
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement