标准kmp+二分

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;

char s[N],p[N];
int ne[N],n; //next[i]表示子串p前i个字符的前缀等于后缀的最长长度

bool check(int lenp){

int lens=strlen(s+1);

//将p的最后字符的后一个设置为非小写英文，使得p的长度变为lenp 
char temp=p[lenp+1];
p[lenp+1]=0;

//标准kmp 

//获取next 
ne[0]=0;ne[1]=0;
for(int i=1,j=0;i<lenp;i++){
	while(j&&p[i+1]!=p[j+1]) j=ne[j];
	if(p[i+1]==p[j+1]) j++;
	ne[i+1]=j;
}

int cnt=0;//计数 

//匹配 
for(int i=0,j=0;i<lens;i++){
	while(j&&p[j+1]!=s[i+1]) j=ne[j];
	if(p[j+1]==s[i+1]) j++;
	if(j==lenp){
		cnt++;
	}
}

//还原p 
p[lenp+1]=temp;

//判断 
if(cnt>=n) return true;
else return false;

}

int main(){
//输入
scanf("%s%s",s+1,p+1);

cin>>n;

int lenp=strlen(p+1);

//二分前的准备 
int l=1,r=lenp,mid;
bool f=false;

//二分答案 
while(l<=r){
	mid=l+r>>1;
	if(check(mid)){
		l=mid+1;
		f=true;
	}else{
		r=mid-1;
	}
}

//判断 
if(f)
	for(int i=1;i<=r;i++){
		cout<<p[i];
	}
else
	cout<<"IMPOSSIBLE"<<endl;
return 0;

}