Submission #1942280

---

Source Code Expand

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> dat;
vector<int> tmp;

int doubles, lengths;

bool compare_suffix(int i, int j)
{
	if (dat[i] == dat[j])
	{
		int ri = (i + doubles <= lengths ? dat[i + doubles] : -1);
		int rj = (j + doubles <= lengths ? dat[j + doubles] : -1);

		return ri < rj;
	}

	return dat[i] < dat[j];
}

vector<int> suffix_array(string S)
{
	lengths = S.size();

	vector<int> arrays(lengths + 1);

	dat.resize(lengths + 1);
	tmp.resize(lengths + 1);

	for (int i = 0; i <= lengths; i++)
	{
		arrays[i] = i;

		dat[i] = i < lengths ? S[i] : -1;
	}

	for (doubles = 1; doubles <= lengths; doubles <<= 1)
	{
		sort(arrays.begin(), arrays.begin() + lengths + 1, compare_suffix);

		tmp[arrays[0]] = 0;

		for (int i = 1; i <= lengths; i++)
		{
			tmp[arrays[i]] = tmp[arrays[i - 1]] + (compare_suffix(arrays[i - 1], arrays[i]) ? 1 : 0);
		}

		for (int i = 0; i <= lengths; i++)
		{
			dat[i] = tmp[i];
		}
	}

	return arrays;
}
string s; int K, cnt[300009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> s >> K;
	int n = s.size();
	for (int i = 0; i < n; i++) cnt[i + 1] = cnt[i] + (s[i] != 'a');
	if (cnt[n] <= K) cout << string(n - K, 'a') << '\n';
	else {
		int ca = 0;
		for (int i = 0; i <= n && cnt[i] <= K; i++) ca = max(ca, i + K - cnt[i]);
		vector<int> sp;
		for (int i = 0; i <= n && cnt[i] <= K; i++) {
			if (i + K - cnt[i] == ca) sp.push_back(i);
		}
		vector<int> sa = suffix_array(s), inv(s.size() + 1);
		for (int i = 0; i <= n; i++) inv[sa[i]] = i;
		int np = -1, pos = -1;
		for (int i : sp) {
			if (np == -1 || (np > inv[i])) {
				np = inv[i];
				pos = i;
			}
		}
		cout << string(ca, 'a') + s.substr(pos) << '\n';
	}
	return 0;
}

Submission Info

Judge Result