/* “Whether you think you can or you think you can’t, you’re right” - Henry Ford */
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#define pl pair<ll, ll>
#define vl vector<ll>
#define vi vector<int>
#define endl '\n'
template <typename T, typename TT>
ostream &operator<<(ostream &os, const pair<T, TT> &t)
{
return os << t.first << " " << t.second;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &t)
{
for (auto &i : t)
os << i << " ";
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
for (T &t : v)
is >> t;
return is;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, vector<pair<T1, T2>> &v)
{
for (pair<T1, T2> &t : v)
is >> t.first >> t.second;
return is;
}
const ll mod = 1e9 + 7;
random_device rd;
uniform_int_distribution<int> dist(100, mod);
const ll p1 = dist(rd), p2 = dist(rd);
ll modpow(ll n, ll p)
{
ll ans = 1;
while (p)
{
if (p & 1)
(ans *= n) %= mod;
(n *= n) %= mod, p /= 2;
}
return ans;
}
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
bitset<mod> mp1, mp2;
vi ah1, ah2, bh1, bh2;
int n, m;
bool check(int mid)
{
mp1.reset(), mp2.reset();
ll pw1 = modpow(p1, mid), pw2 = modpow(p2, mid);
for (int i = mid; i <= n; i++)
{
mp1[(ah1[i] - ((ah1[i - mid] * pw1)%mod) + mod) % mod] = 1;
mp2[(ah2[i] - ((ah2[i - mid] * pw2) % mod) + mod) % mod] = 1;
}
for (int i = mid; i <= m; i++)
{
int h1 = (bh1[i] - ((bh1[i - mid] * pw1)%mod) + mod) % mod,
h2 = (bh2[i] - ((bh2[i - mid] * pw2)%mod) + mod) % mod;
if(mp1[h1] and mp2[h2]) return 1;
}
return 0;
}
void solve()
{
string a, b;
cin >> a >> b;
n = a.size(), m = b.size();
ah1.resize(n + 1), ah2.resize(n + 1), bh1.resize(m + 1), bh2.resize(m + 1);
for (int i = 1; i <= n; i++)
{
ah1[i] = (ah1[i - 1] * p1 + a[i - 1]) % mod;
ah2[i] = (ah2[i - 1] * p2 + a[i - 1]) % mod;
}
for (int i = 1; i <= m; i++)
{
bh1[i] = (bh1[i - 1] * p1 + b[i - 1]) % mod;
bh2[i] = (bh2[i - 1] * p2 + b[i - 1]) % mod;
}
int lo = 1, hi = min(n, m), ans = 0, mid;
while (lo <= hi)
{
mid = lo + (hi - lo) / 2;
if (check(mid))
ans = mid, lo = mid + 1;
else
hi = mid - 1;
}
cout << ans << endl;
}
int main()
{
fast;
ll t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
Lyog4oCcV2hldGhlciB5b3UgdGhpbmsgeW91IGNhbiBvciB5b3UgdGhpbmsgeW91IGNhbuKAmXQsIHlvdeKAmXJlIHJpZ2h04oCdIC0gSGVucnkgRm9yZCAqLwoKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwojZGVmaW5lIGZhc3QgICAgICAgICAgICAgICAgICAgICAgXAogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgXAogICAgY2luLnRpZSgwKTsgICAgICAgICAgICAgICAgICAgXAogICAgY291dC50aWUoMCk7CiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSwgeC5lbmQoKQojZGVmaW5lIEYgZmlyc3QKI2RlZmluZSBTIHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIHBsIHBhaXI8bGwsIGxsPgojZGVmaW5lIHZsIHZlY3RvcjxsbD4KI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIGVuZGwgJ1xuJwoKdGVtcGxhdGUgPHR5cGVuYW1lIFQsIHR5cGVuYW1lIFRUPgpvc3RyZWFtICZvcGVyYXRvcjw8KG9zdHJlYW0gJm9zLCBjb25zdCBwYWlyPFQsIFRUPiAmdCkKewogICAgcmV0dXJuIG9zIDw8IHQuZmlyc3QgPDwgIiAiIDw8IHQuc2Vjb25kOwp9CnRlbXBsYXRlIDx0eXBlbmFtZSBUPgpvc3RyZWFtICZvcGVyYXRvcjw8KG9zdHJlYW0gJm9zLCBjb25zdCB2ZWN0b3I8VD4gJnQpCnsKICAgIGZvciAoYXV0byAmaSA6IHQpCiAgICAgICAgb3MgPDwgaSA8PCAiICI7CiAgICByZXR1cm4gb3M7Cn0KdGVtcGxhdGUgPHR5cGVuYW1lIFQ+CmlzdHJlYW0gJm9wZXJhdG9yPj4oaXN0cmVhbSAmaXMsIHZlY3RvcjxUPiAmdikKewogICAgZm9yIChUICZ0IDogdikKICAgICAgICBpcyA+PiB0OwogICAgcmV0dXJuIGlzOwp9CnRlbXBsYXRlIDx0eXBlbmFtZSBUMSwgdHlwZW5hbWUgVDI+CmlzdHJlYW0gJm9wZXJhdG9yPj4oaXN0cmVhbSAmaXMsIHZlY3RvcjxwYWlyPFQxLCBUMj4+ICZ2KQp7CiAgICBmb3IgKHBhaXI8VDEsIFQyPiAmdCA6IHYpCiAgICAgICAgaXMgPj4gdC5maXJzdCA+PiB0LnNlY29uZDsKICAgIHJldHVybiBpczsKfQoKY29uc3QgbGwgbW9kID0gMWU5ICsgNzsKcmFuZG9tX2RldmljZSByZDsKdW5pZm9ybV9pbnRfZGlzdHJpYnV0aW9uPGludD4gZGlzdCgxMDAsIG1vZCk7CmNvbnN0IGxsIHAxID0gZGlzdChyZCksIHAyID0gZGlzdChyZCk7CgpsbCBtb2Rwb3cobGwgbiwgbGwgcCkKewogICAgbGwgYW5zID0gMTsKICAgIHdoaWxlIChwKQogICAgewogICAgICAgIGlmIChwICYgMSkKICAgICAgICAgICAgKGFucyAqPSBuKSAlPSBtb2Q7CiAgICAgICAgKG4gKj0gbikgJT0gbW9kLCBwIC89IDI7CiAgICB9CiAgICByZXR1cm4gYW5zOwp9CgpzdHJ1Y3QgY3VzdG9tX2hhc2gKewogICAgc3RhdGljIHVpbnQ2NF90IHNwbGl0bWl4NjQodWludDY0X3QgeCkKICAgIHsKICAgICAgICB4ICs9IDB4OWUzNzc5Yjk3ZjRhN2MxNTsKICAgICAgICB4ID0gKHggXiAoeCA+PiAzMCkpICogMHhiZjU4NDc2ZDFjZTRlNWI5OwogICAgICAgIHggPSAoeCBeICh4ID4+IDI3KSkgKiAweDk0ZDA0OWJiMTMzMTExZWI7CiAgICAgICAgcmV0dXJuIHggXiAoeCA+PiAzMSk7CiAgICB9CiAgICBzaXplX3Qgb3BlcmF0b3IoKSh1aW50NjRfdCB4KSBjb25zdAogICAgewogICAgICAgIHN0YXRpYyBjb25zdCB1aW50NjRfdCBGSVhFRF9SQU5ET00gPSBjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCk7CiAgICAgICAgcmV0dXJuIHNwbGl0bWl4NjQoeCArIEZJWEVEX1JBTkRPTSk7CiAgICB9Cn07CgpiaXRzZXQ8bW9kPiBtcDEsIG1wMjsKdmkgYWgxLCBhaDIsIGJoMSwgYmgyOwppbnQgbiwgbTsKYm9vbCBjaGVjayhpbnQgbWlkKQp7CiAgICBtcDEucmVzZXQoKSwgbXAyLnJlc2V0KCk7CiAgICBsbCBwdzEgPSBtb2Rwb3cocDEsIG1pZCksIHB3MiA9IG1vZHBvdyhwMiwgbWlkKTsKICAgIGZvciAoaW50IGkgPSBtaWQ7IGkgPD0gbjsgaSsrKQogICAgewogICAgICAgIG1wMVsoYWgxW2ldIC0gKChhaDFbaSAtIG1pZF0gKiBwdzEpJW1vZCkgKyAgbW9kKSAlIG1vZF0gPSAxOwogICAgICAgIG1wMlsoYWgyW2ldIC0gKChhaDJbaSAtIG1pZF0gKiBwdzIpICUgbW9kKSArIG1vZCkgJSBtb2RdID0gMTsKICAgIH0KICAgIGZvciAoaW50IGkgPSBtaWQ7IGkgPD0gbTsgaSsrKQogICAgewogICAgICAgIGludCBoMSA9IChiaDFbaV0gLSAoKGJoMVtpIC0gbWlkXSAqIHB3MSklbW9kKSArIG1vZCkgJSBtb2QsCiAgICAgICAgICAgIGgyID0gKGJoMltpXSAtICgoYmgyW2kgLSBtaWRdICogcHcyKSVtb2QpICsgbW9kKSAlIG1vZDsKICAgICAgICBpZihtcDFbaDFdIGFuZCBtcDJbaDJdKSByZXR1cm4gMTsKICAgIH0KICAgIHJldHVybiAwOwp9Cgp2b2lkIHNvbHZlKCkKewogICAgc3RyaW5nIGEsIGI7CiAgICBjaW4gPj4gYSA+PiBiOwogICAgbiA9IGEuc2l6ZSgpLCBtID0gYi5zaXplKCk7CiAgICBhaDEucmVzaXplKG4gKyAxKSwgYWgyLnJlc2l6ZShuICsgMSksIGJoMS5yZXNpemUobSArIDEpLCBiaDIucmVzaXplKG0gKyAxKTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykKICAgIHsKICAgICAgICBhaDFbaV0gPSAoYWgxW2kgLSAxXSAqIHAxICsgYVtpIC0gMV0pICUgbW9kOwogICAgICAgIGFoMltpXSA9IChhaDJbaSAtIDFdICogcDIgKyBhW2kgLSAxXSkgJSBtb2Q7CiAgICB9CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBtOyBpKyspCiAgICB7CiAgICAgICAgYmgxW2ldID0gKGJoMVtpIC0gMV0gKiBwMSArIGJbaSAtIDFdKSAlIG1vZDsKICAgICAgICBiaDJbaV0gPSAoYmgyW2kgLSAxXSAqIHAyICsgYltpIC0gMV0pICUgbW9kOwogICAgfQogICAgaW50IGxvID0gMSwgaGkgPSBtaW4obiwgbSksIGFucyA9IDAsIG1pZDsKICAgIHdoaWxlIChsbyA8PSBoaSkKICAgIHsKICAgICAgICBtaWQgPSBsbyArIChoaSAtIGxvKSAvIDI7CiAgICAgICAgaWYgKGNoZWNrKG1pZCkpCiAgICAgICAgICAgIGFucyA9IG1pZCwgbG8gPSBtaWQgKyAxOwogICAgICAgIGVsc2UKICAgICAgICAgICAgaGkgPSBtaWQgLSAxOwogICAgfQogICAgY291dCA8PCBhbnMgPDwgZW5kbDsKfQoKaW50IG1haW4oKQp7CiAgICBmYXN0OwogICAgbGwgdCA9IDE7CiAgICAvLyBjaW4gPj4gdDsKICAgIHdoaWxlICh0LS0pCiAgICB7CiAgICAgICAgc29sdmUoKTsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==