fork download
copy 
  1. /* “Whether you think you can or you think you can’t, you’re right” - Henry Ford */
  2.  
  3. #pragma GCC optimize("Ofast")
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. typedef long long ll;
  7. #define fast                      \
  8.     ios_base::sync_with_stdio(0); \
  9.     cin.tie(0);                   \
  10.     cout.tie(0);
  11. #define all(x) x.begin(), x.end()
  12. #define F first
  13. #define S second
  14. #define pb push_back
  15. #define pl pair<ll, ll>
  16. #define vl vector<ll>
  17. #define vi vector<int>
  18. #define endl '\n'
  19.  
  20. template <typename T, typename TT>
  21. ostream &operator<<(ostream &os, const pair<T, TT> &t)
  22. {
  23.     return os << t.first << " " << t.second;
  24. }
  25. template <typename T>
  26. ostream &operator<<(ostream &os, const vector<T> &t)
  27. {
  28.     for (auto &i : t)
  29.         os << i << " ";
  30.     return os;
  31. }
  32. template <typename T>
  33. istream &operator>>(istream &is, vector<T> &v)
  34. {
  35.     for (T &t : v)
  36.         is >> t;
  37.     return is;
  38. }
  39. template <typename T1, typename T2>
  40. istream &operator>>(istream &is, vector<pair<T1, T2>> &v)
  41. {
  42.     for (pair<T1, T2> &t : v)
  43.         is >> t.first >> t.second;
  44.     return is;
  45. }
  46.  
  47. const ll mod = 1e9 + 7;
  48. random_device rd;
  49. uniform_int_distribution<int> dist(100, mod);
  50. const ll p1 = dist(rd), p2 = dist(rd);
  51.  
  52. ll modpow(ll n, ll p)
  53. {
  54.     ll ans = 1;
  55.     while (p)
  56.     {
  57.         if (p & 1)
  58.             (ans *= n) %= mod;
  59.         (n *= n) %= mod, p /= 2;
  60.     }
  61.     return ans;
  62. }
  63.  
  64. struct custom_hash
  65. {
  66.     static uint64_t splitmix64(uint64_t x)
  67.     {
  68.         x += 0x9e3779b97f4a7c15;
  69.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  70.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  71.         return x ^ (x >> 31);
  72.     }
  73.     size_t operator()(uint64_t x) const
  74.     {
  75.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  76.         return splitmix64(x + FIXED_RANDOM);
  77.     }
  78. };
  79.  
  80. bitset<mod> mp1, mp2;
  81. vi ah1, ah2, bh1, bh2;
  82. int n, m;
  83. bool check(int mid)
  84. {
  85.     mp1.reset(), mp2.reset();
  86.     ll pw1 = modpow(p1, mid), pw2 = modpow(p2, mid);
  87.     for (int i = mid; i <= n; i++)
  88.     {
  89.         mp1[(ah1[i] - ((ah1[i - mid] * pw1)%mod) +  mod) % mod] = 1;
  90.         mp2[(ah2[i] - ((ah2[i - mid] * pw2) % mod) + mod) % mod] = 1;
  91.     }
  92.     for (int i = mid; i <= m; i++)
  93.     {
  94.         int h1 = (bh1[i] - ((bh1[i - mid] * pw1)%mod) + mod) % mod,
  95.             h2 = (bh2[i] - ((bh2[i - mid] * pw2)%mod) + mod) % mod;
  96.         if(mp1[h1] and mp2[h2]) return 1;
  97.     }
  98.     return 0;
  99. }
  100.  
  101. void solve()
  102. {
  103.     string a, b;
  104.     cin >> a >> b;
  105.     n = a.size(), m = b.size();
  106.     ah1.resize(n + 1), ah2.resize(n + 1), bh1.resize(m + 1), bh2.resize(m + 1);
  107.     for (int i = 1; i <= n; i++)
  108.     {
  109.         ah1[i] = (ah1[i - 1] * p1 + a[i - 1]) % mod;
  110.         ah2[i] = (ah2[i - 1] * p2 + a[i - 1]) % mod;
  111.     }
  112.     for (int i = 1; i <= m; i++)
  113.     {
  114.         bh1[i] = (bh1[i - 1] * p1 + b[i - 1]) % mod;
  115.         bh2[i] = (bh2[i - 1] * p2 + b[i - 1]) % mod;
  116.     }
  117.     int lo = 1, hi = min(n, m), ans = 0, mid;
  118.     while (lo <= hi)
  119.     {
  120.         mid = lo + (hi - lo) / 2;
  121.         if (check(mid))
  122.             ans = mid, lo = mid + 1;
  123.         else
  124.             hi = mid - 1;
  125.     }
  126.     cout << ans << endl;
  127. }
  128.  
  129. int main()
  130. {
  131.     fast;
  132.     ll t = 1;
  133.     // cin >> t;
  134.     while (t--)
  135.     {
  136.         solve();
  137.     }
  138.     return 0;
  139. }
  140.  
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/4nLFAv
problem ADAPHOTO, based on SPOJ submission 26510565 (CPP14), 2020-08-31 10:06:01
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!