题解

太显然了，二分套KMP板子直接秒。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
string s1, s2;
int n;
vector<int> prefix_function(string &s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}
vector<int> find_occurrences(string &text, string &pattern) {
  string cur = pattern + '#' + text;
  int sz1 = text.size(), sz2 = pattern.size();
  vector<int> v;
  vector<int> lps = prefix_function(cur);
  for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
    if (lps[i] == sz2) v.push_back(i - 2 * sz2);
  }
  return v;
}
//成 功 的 路 上 总 要 失 去 什 么 
bool check(int tmp){
	string s = s2.substr(0, tmp);
	return (find_occurrences(s1, s).size() >= n);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s1 >> s2 >> n;
	int l = 1, r = s2.size();
	while(l <= r){//二分
		int mid = l + r >> 1;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	if(r < 1) cout << "IMPOSSIBLE";
	else cout << s2.substr(0, r);

	return 0;
}