题解

明显的二分。

注意到暴力截取字符串再判断相等的复杂度过高，所以考虑维护一个字符串哈希。我好唐啊不会写KMP

AC Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
const ull BASE=233;
ll n,l,r;
ull pows[100005],ha[100005];
string a,b;
inline ull gethash(ll l,ll r){
    if(l==0) return ha[r];
    return ha[r]-ha[l-1]*pows[r-l+1];
}
inline bool can(const ll &mid){
    ll res=0;
    string x=b.substr(0,mid);
    ull xha=x[0];
    for(ll i=1;i<x.size();i++) xha=xha*BASE+x[i];
    for(ll i=mid-1;i<a.size();i++) if(gethash(i-mid+1,i)==xha) res++;
    return res>=n;
}
int main(){
    cin>>a>>b>>n;
    for(ll i=0;i<a.size();i++){
        if(i==0) ha[i]=a[i],pows[i]=1;
        else ha[i]=ha[i-1]*BASE+a[i],pows[i]=pows[i-1]*BASE;
    }
    l=1,r=b.size();
    while(r-l>=3){
        ll mid=l+r>>1;
        if(can(mid)) l=mid;
        else r=mid;
    }
    while(l<=r){
        if(can(r)){
            cout<<b.substr(0,r);
            return 0;
        }
        r--;
    }
    cout<<"IMPOSSIBLE";
    return 0;
}