PROG-1019: DNA

#include <bits/stdc++.h>
using namespace std;
// PPPPPPP-PP
using lli = long long;
using pii = pair <lli, int>;
const lli PB = 98765431;
const lli INF = 2e18;

string str[2];
int found(set <lli> S1, set<lli> S2, vector<lli> pst){
    for(auto s:S1){
        if(S2.find(s) != S2.end()) {
            for(int i=0; i<pst.size();i++){
                if(pst[i] == s) return i;
            }
        }
    }
    return -1;
}

int hashing(int n){

    lli hsh[2] = {0}, rem = 1;
    set <lli> S[2];
    vector <lli> pst;
    for(int i=0; i<n; i++){
        if(i != 0) rem *= PB;
        for(int j=0;j<2;j++) hsh[j] = hsh[j]*PB + str[j][i];
    }
    for(int j=0;j<2;j++){
        for(int i=0; i<=str[j].size()-n; i++){
            if(i != 0) hsh[j] = hsh[j]*PB + str[j][i+n-1];
            if(j == 0) pst.push_back(hsh[j]);
            S[j].insert(hsh[j]);
            hsh[j] = hsh[j] - rem*str[j][i];
        }
    }

    return found(S[0],S[1],pst);
}

int main(){

    cin>>str[0];
    cin>>str[1];

    int sz = min(str[0].size(), str[1].size()), l=0, r=sz, mid, mx=0, pst;
    while(l <= r){
        mid = (l+r)/2;
        int p = hashing(mid);
        if(p != -1){
            mx = max(mx, mid);
            pst = p;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    for(int i=pst; i<=pst+mx-1; i++) printf("%c",str[0][i]);

    return 0;
}