sufar nlogn slow

sufar.cpp

vector<int> sufar(string s) {
	int n = size(s);
	vector<int> p(n), c(n); 
	iota(begin(p), end(p), 0);
	sort(begin(p), end(p), [&](int i, int j) { return s[i] < s[j]; });
	for(int i=1; i<n; ++i) c[p[i]] = c[p[i-1]] + (s[p[i]]!=s[p[i-1]]);
	for(int k=1; k<n; k*=2) {
		vector<vector<pair<int,int>>> f(n);
		for(int i : p) {
			int j = i - k; if(j < 0) j += n;
			f[c[j]].emplace_back(c[i], j);
		}
		int cn = 0, i = 0;
		for(auto &v : f) {
			int x = -1;
			for(auto &[ci, j] : v) {
				p[i++] = j;
				if(ci != x) ++cn, x = ci;
				c[j] = cn - 1;
			}
		}
		if(cn == n) break;
	}
	return p;
}