Submission #1016494

---

Source Code Expand

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


struct compare_sa{
	const vector<int> &rank;
	int n, k;
	compare_sa(const vector<int> &rank, int n, int k) : rank(rank), n(n), k(k) {}
		bool operator () (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;
	}
};

vector<int> create_sa(const string& s){
	int n = s.length();
	vector<int> sa(n + 1, -1);
	vector<int> rank(n + 1, -1);
	vector<int> tmp(n + 1, -1);

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

	for (int k=1;k<=n;k*=2){
		compare_sa cp = compare_sa(rank, n, k);
		sort(sa.begin(),sa.begin()+n+1,cp);
		tmp[sa[0]] = 0;
		for(int i=1;i<=n;i++){
			tmp[sa[i]] = tmp[sa[i - 1]] + (cp(sa[i - 1], sa[i]) ? 1 : 0);
		}
		for (int i=0;i<=n;i++) {
			rank[i] = tmp[i];
		}
	}
	
	return sa;
}

int main(void){
	int k;
	string s;
	cin >> k >> s;
	if (k == 0) {
		cout << s << endl;
		return 0;
	}
	
	int n = s.length();
	vector<int> sa = create_sa(s);
	vector<int> sa_inv(n + 1);
	
	for(int i=0;i<n+1;i++){
		sa_inv[sa[i]] = i;
	}
	
	vector<int> sat;
	int q = (n + k) / (k + 1);
	int r = q * (k + 1) - n;
	
	for(int i=0;i<sa.size();i++){
		int w = sa[i];
		if (w <= n - q) {
			sat.push_back(w);
		}
	}
	
	int lo = -1;
	int hi = n - q + 1;
	while (hi - lo > 1){
		int mid = (hi + lo) / 2;
		int rem = r;
		for(int i=0;i<k+1;i++){
			if (rem < 0){
				break;
			}
			int idx = i * q - r + rem;
			if (idx >= n - q + 1){
				break;
			}
			if (sa_inv[idx] > sa_inv[sat[mid]]) {
				rem--;
			}
		}
		if (rem >= 0){
			hi = mid;
		}
		else {
			lo = mid;
		}
	}
	
	cout << s.substr(sat[hi], q) << endl;
	return 0;
}

Submission Info

Judge Result