通俗易懂

模板题

两个函数

KMP( )判断是否合法

NEXT( )获取next数组

主函数二分带入函数

#include<bits/stdc++.h>
using namespace std;
string s1, s2;
int n;
void NEXT(vector<int> &nxt, string x) {
	int i = 1, len = 0;
	nxt[0] = 0;
	while (i < x.size()) {
		if (x[i] == x[len]) nxt[i++] = ++len;
		else {
			if (len) len = nxt[len - 1];
			else nxt[i++] = 0;
		}
	}
}
bool KMP(string y) {
	int N = s1.size();
	int M = y.size();
	int cnt = 0;
	vector<int> next(M, 0);
	NEXT(next, y);
	int i = 0, j = 0;
	while (i < N) {
		if (s1[i] == y[j]) {
			i++;
			j++;
		}
		if (j == M) {
			cnt++;
			j = next[j - 1];
		} else if (s1[i] != y[j] && i < N) {
			if (j) j = next[j - 1];
			else i++;
		}
	}
	if (cnt >= n) return 1;
	else return 0;
}
int main() {
	cin >> s1 >> s2 >> n;
	string x, k;
	int l = 1, r = s2.size(), m, ans = 0;
	while (l <= r) {
		m = l + r >> 1;
		x = s2.substr(0, m);
		if (KMP(x)) {
			ans = m;
			k = x;
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	if (ans) cout << k;
	else cout << "IMPOSSIBLE";
	return 0;
}