Submission #1796959

---

Source Code Expand

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

class SuffixArray {
	const int n;
	string S;
public:
	vector<int> sa, rank;
	SuffixArray(const string &S_)
		: n(S_.size()), S(S_), sa(n + 1), rank(n + 1)
	{
		for (int i = 0; i <= n; i++) {
			sa[i] = i;
			rank[i] = i < n ? S[i] : -1;
		}
		vector<int> tmp(n + 1);
		for (int k = 1; k <= n; k *= 2) {
			auto Compare_SA = [=](int i, int j) {
				if (rank[i] != rank[j]) return rank[i] < rank[j];

				int ri = i + k <= n ? rank[i + k] : -1;
				int rj = j + k <= n ? rank[j + k] : -1;
				return ri < rj;
			};
			sort(sa.begin(), sa.end(), Compare_SA);

			tmp[sa[0]] = 0;
			for (int i = 1; i <= n; i++) {
				tmp[sa[i]] = tmp[sa[i - 1]] + (Compare_SA(sa[i - 1], sa[i]) ? 1 : 0);
			}
			for (int i = 0; i <= n; i++) {
				rank[i] = tmp[i];
			}
		}
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	string S;
	int K;
	cin >> S >> K;
	int N = S.size();
	vector<int> cnt(N + 1);
	int en = N;
	for (int i = 0; i < N; i++) {
		cnt[i + 1] = cnt[i] + (S[i] == 'a');
		if (i + 1 - cnt[i + 1] > K  && en == N) en = i;
	}
	if (cnt.back() + K >= N) {
		cout << string(N - K, 'a') << endl;
		return 0;
	}
	SuffixArray sa(S);
	int pos = -1;
	for (int i = 0; i < N; i++) {
		if (sa.sa[i] <= en && (pos == -1 || cnt[pos] < cnt[sa.sa[i]])) {
			pos = sa.sa[i];
		}
	}
	cout << string(K + cnt[pos], 'a') << S.substr(pos, N - pos) << endl;
	return 0;
}

Submission Info

Judge Result