Proficient.
Put your skills to the test.

Problem summary

Find the longest substring of S1 occurring at least K times in S2, allowing overlaps. Break equal-length ties lexicographically.

Constraints

1 ≤ N,M,K ≤ 100000; alphabet A,C,G,T; a nonempty answer is guaranteed.

Worked example

An independently prepared example for this explanation.

7 19 3
GATTACA
TACATTACGCATTACACAT

ACA

Solution analysis

1. Build the suffix array of S1+# +S2, using a separator absent from DNA, then compute adjacent longest-common-prefix values with Kasai’s algorithm. Prefix doubling with counting sorts keeps construction deterministic and O(L log L).
2. For a proposed length d, partition suffix-array order wherever adjacent LCP is below d. Within each group, all suffixes share a length-d prefix. The length is feasible exactly when some group contains a suffix starting in S1 and at least K suffixes starting in S2. Binary search the largest feasible d.
3. After finding d, scan groups once more. The first qualifying group gives the lexicographically smallest prefix. In the example the longest eligible length is three; ACA,CAT,TAC each occur at least three times in S2, and ACA is first lexicographically. Occurrences are suffix starts, so overlaps are naturally counted.

Why it works

Adjacent LCP values at least d connect exactly the suffixes sharing one prefix of length d; equality of a fixed prefix is contiguous in sorted order. Thus the group test is equivalent to the problem condition. A feasible substring has feasible shorter prefixes, justifying binary search. Finally suffix-array group order is lexicographic order of their prefixes, proving the tie-break.

Watch out. Count occurrences in S2 only. The separator prevents a substring from crossing the end of S1. Hash collisions are avoided entirely.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<numeric>
// Algorithm: Build the suffix array of S1+# +S2, using a separator absent from DNA, then compute
// adjacent longest-common-prefix values with Kasai’s algorithm.
using namespace std;
vector<int>suffixArray(const string&text){
    int n=static_cast<int>(text.size());
    vector<int>order(n),rank(n),temporary(n),nextRank(n);
    iota(order.begin(),order.end(),0);
    for(int i=0;i<n;++i){
        rank[i]=static_cast<unsigned char>(text[i]);
    }
    int classes=256;
    auto countingSort=[&](int offset){
        vector<int>count(classes+1,0);
        for(int index:order){
            ++count[index+offset<n?rank[index+offset]+1:0];
        }
        int sum=0;
        for(int&amount:count){
            int old=amount;
            amount=sum;
            sum+=old;
        }
        for(int index:order){
            int key=index+offset<n?rank[index+offset]+1:0;
            temporary[count[key]++]=index;
        }
        order.swap(temporary);
    };
    for(int width=1;width<n;width*=2){
        countingSort(width);
        countingSort(0);
        int distinct=1;
        nextRank[order[0]]=0;
        for(int i=1;i<n;++i){
            int a=order[i-1],b=order[i];
            int secondA=a+width<n?rank[a+width]:-1;
            int secondB=b+width<n?rank[b+width]:-1;
            if(rank[a]!=rank[b]||secondA!=secondB){
                ++distinct;
            }
            nextRank[b]=distinct-1;
        }
        rank.swap(nextRank);
        classes=distinct;
        if(classes==n){
            break;
        }
    }
    return order;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,required;
    string first,second;
    cin>>n>>m>>required>>first>>second;
    string text=first+'#'+second;
    int length=static_cast<int>(text.size());
    vector<int>order=suffixArray(text),position(length),lcp(length,0);
    for(int i=0;i<length;++i){
        position[order[i]]=i;
    }
    int common=0;
    for(int i=0;i<length;++i){
        int rank=position[i];
        if(rank==0){
            common=0;
            continue;
        }
        int previous=order[rank-1];
        while(i+common<length&&previous+common<length&&
            text[i+common]==text[previous+common]){
            ++common;
        }
        lcp[rank]=common;
        if(common>0){
            --common;
        }
    }
    auto candidate=[&](int size){
        int group=0;
        while(group<length){
            int end=group+1;
            while(end<length&&lcp[end]>=size){
                ++end;
            }
            int fromFirst=-1,occurrences=0;
            for(int i=group;i<end;++i){
                if(order[i]<n&&order[i]+size<=n){
                    fromFirst=order[i];
                }
                if(order[i]>n&&order[i]+size<=length){
                    ++occurrences;
                }
            }
            if(fromFirst!=-1&&occurrences>=required){
                return fromFirst;
            }
            group=end;
        }
        return -1;
    };
    int low=1,high=min(n,m);
    while(low<high){
        int middle=(low+high+1)/2;
        if(candidate(middle)!=-1){
            low=middle;
        }
        else{
            high=middle-1;
        }
    }
    cout<<first.substr(candidate(low),low)<<'\n';
}