Untitled

 avatar
unknown
plain_text
a month ago
1.0 kB
2
Indexable
string s1, s2;
unordered_map<ll, bool> mp;
ll h1[inf], h2[inf], p[inf];
int n;
 
void nhap()
{
    cin >> s1 >> s2;
}
 
bool check(int len)
{
    int cnt = 0;
    FORD(i, 1, n)
    {
        ll cur = h1[i + len - 1] - h1[i - 1] * p[len] + m2;
        mp[cur] = 1;
    }
    FORD(i, 1, n)
    {
        ll cur = h2[i + len - 1] - h2[i - 1] * p[len] + m2;
        if(mp[cur]) cnt++;
    }
    return cnt >= 1;
}
 
void solve()
{
    nhap();
    n = s1.size();
    s1 = " " + s1 + s1;
    s2 = " " + s2 + s2;
    h1[0] = h2[0] = 0;
    p[0] = 1;
    FORD(i, 1, n * 2) p[i] = p[i - 1] * base;
    FORD(i, 1, n * 2)
    {
        h1[i] = h1[i - 1] * base + s1[i];
        h2[i] = h2[i - 1] * base + s2[i];
    }
    int l = 1, r = n, res = 0;
    while(r - l >= 0)
    {
        int m = l + (r - l) / 2;
        if(check(m))
        {
            res = m;
            l = m + 1;
        }
        else
        {
            r = m - 1;
        }
    }
    cout << res;
}
Leave a Comment