Submission #1796927

---

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();
	int cnt = 0, en = -1;
	for (int i = 0; i < N; i++) {
		if (S[i] != 'a') {
			cnt++;
			if (cnt > K && en == -1) en = i;
		}
	}
	if (K >= cnt) {
		cout << string(N - K, 'a') << endl;
		return 0;
	}
	SuffixArray sa(S);
	int pos = 0;
	for (int i = 0; i < N; i++) {
		if (sa.sa[i] <= en && S[sa.sa[i]] != 'a') {
			pos = sa.sa[i];
			break;
		}
	}
	cnt = 0;
	for (int i = 0; i < pos; i++) {
		if (S[i] != 'a') {
			cnt++;
		}
	}
	cout << string(pos + (K - cnt), 'a') << S.substr(pos, N - pos) << endl;
	return 0;
}

Submission Info

Judge Result