F-Random Strings, C++ (gcc)

Language: Layout:

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

struct SuffixTree{
	int cur, prv, pos, phase, extn;
	vector<int> l, r, p, link;
	vector< vector<int> > node, child;
	int N, n;
	string s;
	vector<int> sum;
 
	SuffixTree(string x){
		s = x + "$";
		N = s.length()*2 + 5;
		l.resize(N, 0), r.resize(N, 0), p.resize(N, 0), link.resize(N, -1), sum.resize(N, 0);
		node.resize(N, vector<int>(27, -1));
		child.resize(N);
		cur = 0, prv = -1, pos = 0, l[0] = r[0] = -1, link[0] = 0, n = 1;
		build();
        dfs(0);
	}	
 
	inline int get(char ch){
		if(ch >= 'a' && ch <= 'z') return (ch - 'a');
		if(ch == '$') return 26;
		assert(1 == 0);
	}
 
	void insert(int x){
		// cout << x << endl;
		while(extn < phase){
			if(pos <= r[cur]){
				if(get(s[pos]) == x){
					// RULE 3
					pos++; break;
				}
				extn ++;
				int md = n, leaf = n+1; n += 2;
				if(prv != -1) link[prv] = md; prv = md;
				p[md] = p[cur], p[cur] = p[leaf] = md;
				l[md] = l[cur], r[md] = pos-1, l[cur] = pos, l[leaf] = phase, r[leaf] = s.length() - 1;
				node[p[md]][get(s[l[md]])] = md, node[md][get(s[l[cur]])] = cur, node[md][get(s[l[leaf]])] = leaf;
				child[md].pb(get(s[l[cur]])), child[md].pb(get(s[l[leaf]]));
				cur = link[p[md]], pos = l[md] + (p[md] == 0? 1 : 0);
				while(pos <= r[md]) cur = node[cur][get(s[pos])], pos += (r[cur] - l[cur] + 1);
				if(pos == (r[md] + 1)) pos = r[cur] + 1;
				else pos = r[cur] - (pos - r[md] - 1) + 1;
			}
			else{
				if(prv != -1) link[prv] = cur; prv = -1;
				if(node[cur][x] != -1){
					// RULE 3
					cur = node[cur][x], pos = l[cur] + 1; break;
				}
				child[cur].pb(x);
				node[cur][x] = n, l[n] = phase, r[n] = s.length() - 1, p[n] = cur, n += 1;
				cur = link[cur], pos = r[cur]+1;
				extn++;
			}
		}
		if(prv != -1) link[prv] = 0, prv = -1;
	}
    
    void follow_suffix(int &cur, int& pos){
        pos --;
        int t = link[p[cur]], p2 = l[cur] + (p[cur] == 0? 1 : 0);
        while(p2 <= pos) t = node[t][get(s[p2])], p2 += (r[t] - l[t] + 1);
        if(p2 == pos+1) p2 = r[t]+1;
        else p2 = r[t] - (p2 - (pos + 1)) + 1;
        cur = t, pos = p2;
    }

void build(){
		phase = 0, extn = -1;
        while(phase < s.length()) insert(get(s[phase])), phase ++; 
	}
    
    int dfs(int cur){
        if(cur == -1) return 0;
        if(r[cur] == ((int)s.length() - 1)){
            // leaf node
            sum[cur] = 1;
            return 1;
        }
        int ans = 0;
        for(int j = 0; j < 27; j++) ans += dfs(node[cur][j]);
        return (sum[cur] = ans);
    }
    
    bool solve(int& cur, int& pos, int shift, string& s2, int& i){
        if(cur == -1) return 0;
        
        // cout << pos << " " << shift << " " << s2.length() << endl;
        
        while(pos <= r[cur] && shift){
            if(s2[i++] == s[pos++]) shift --;
            else return 0;
        }
        if(!shift) return 1;
        
        if(i == s2.length()) return 0;
        int at = node[cur][get(s2[i])];
        if(at == -1) return 0;
        pos = l[at];
        
        for(; pos <= r[at] && shift; shift--)
            if(s[pos++] != s2[i++]) return 0;
        
        cur = at;
        if(!shift) return 1;
        return solve(cur, pos, shift, s2, i);
    }
};

typedef long long int ll;
const int N = 2e5+5;
const int mod1 = 1e9+7;
const int mod2 = 1e9+9;

vector<ll> pwr1(N, 1), pwr2(N, 1);
vector<ll> inv_pwr1(N, 1), inv_pwr2(N, 1);

ll fast_pow(ll a, ll b, int mod){
    ll ans = 1;
    while(b){
        if(b&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return ans;
}

int foo(int l1, int r1, int l2, int r2, int st1, int st2, vector<ll>& pre1, vector<ll>& pre2){
    if(l1 == r1) return (st1 - l1 + 1);
    int m1 = (l1+r1) >> 1;
    int m2 = (l2+r2) >> 1;
    
    ll lft1 = ((pre1[m1+1] - pre1[st1-1] + mod1) % mod1 * inv_pwr1[st1]) % mod1;
    ll rgt1 = ((pre1[m2+1] - pre1[st2-1] + mod1) % mod1 * inv_pwr1[st2]) % mod1;
    
    ll lft2 = ((pre2[m1+1] - pre2[st1-1] + mod2) % mod2 * inv_pwr2[st1]) % mod2;
    ll rgt2 = ((pre2[m2+1] - pre2[st2-1] + mod2) % mod2 * inv_pwr2[st2]) % mod2;
    
    if(lft1 == rgt1 && lft2 == rgt2) return foo(m1+1, r1, m2+1, r2, st1, st2, pre1, pre2);
    return foo(l1, m1, l2, m2, st1, st2, pre1, pre2);
}

int lex_small(vector<ll>& pre1, vector<ll>& pre2, string& s, int i1, int i2, int K){
    int ind = foo(i1-K+1 + 1, i1+1, i2-K+1 +1, i2+1, i1-K+1+1, i2-K+1+1, pre1, pre2);
    if(ind == 1 && s[i1-K+1] != s[i2-K+1]) ind --;
    
    // cout << "HERE --> " << ind << " " << i1 << " " << i2 << endl;
    if(s[ind+(i1 - K + 1)] > s[ind+(i2 - K + 1)]) return i2;
    return i1;
}

int solve(string& s1, string& s2, int K){
    SuffixTree st1(s1), st2(s2);
    int m = s2.length(), cur1 = 0, cur2 = 0;
    vector<ll> pre1(m+2, 0), pre2(m+2, 0);
    for(int j = 1; j <= m; j++) pre1[j] = (pre1[j-1] + pwr1[j]*((int)s2[j-1]) % mod1) % mod1;
    for(int j = 1; j <= m; j++) pre2[j] = (pre2[j-1] + pwr2[j]*((int)s2[j-1]) % mod2) % mod2;
    
    int pos1 = 0, pos2 = 0, st = 0;
    int ans = 0, ind = -1, i1 = 0, i2 = 0;
    for(int j = K-1; j < m; j++){
        if((j - st + 1) < K) continue;
        
        int x1 = st1.solve(cur1, pos1, (j - i1 + 1), s2, i1);
        int x2 = st2.solve(cur2, pos2, (j - i2 + 1), s2, i2);
        // cout << st << " " << j << " -> "  << i1 << " " << i2 << endl;
        
        if(!x1 || !x2){
            st = i1 = i2 = i1 + 1;
            j = st + (K - 1);
            cur1 = cur2 = pos1 = pos2 = 0;
            j--;
            continue;
        }
        int aft = st1.sum[cur1] + st2.sum[cur2];
        // cout << aft << " -> " << st1.sum[cur1] << " " << st2.sum[cur2] << endl;
        if(aft > ans) ans = aft, ind = j;
        else if(aft == ans) ind = lex_small(pre1, pre2, s2, ind, j, K);
        
        st++;
        st1.follow_suffix(cur1, pos1);
        st2.follow_suffix(cur2, pos2);
        // cout << cur1 << " " << st1.l[cur1] << " " << st1.r[cur1]  << " " << pos1 << ",  " << pos2 << endl;
    }
    return ind;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    const int PRM1 = 37, PRM2 = 29;
    for(int j = 1; j < N; j++) pwr1[j] = (pwr1[j-1] * PRM1) % mod1, inv_pwr1[j] = fast_pow(pwr1[j], mod1-2, mod1);
    for(int j = 1; j < N; j++) pwr2[j] = (pwr2[j-1] * PRM2) % mod2, inv_pwr2[j] = fast_pow(pwr2[j], mod2-2, mod2);
    
	int t;
    cin >> t;
    while(t--){
        int n, m, K;
        cin >> n >> m >> K;
        string s1, s2;
        cin >> s1 >> s2;
        
        int ans = solve(s1, s2, K);
        if(ans == -1) cout << ans << '\n';
        else{
            string x = "";
            for(int j = ans-K+1; j <= ans; j++) x += s2[j];
            cout << x << '\n';
        }
    }
	return 0;
}

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 2.33 sec, absolute running time: 0.13 sec, cpu time: 0.11 sec, memory peak: 7 Mb, absolute service time: 2,47 sec