Suffix array creation in O(n log^{2} n)

main.cpp

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <array>
#include <algorithm>

struct Prefix {
	std::string& source;
	int offset;
	int rank[4];

	Prefix(std::string &subject, int offset): source(subject), offset(offset) {
		rank[0] = subject[offset];
		if(offset + 1 >= subject.length()){
			rank[1] = -1;
		} else {
			rank[1] = subject[offset + 1];
		}
		rank[2] = 0;
		rank[3] = 0;
	}
	
	Prefix& operator=(const Prefix& other) {
		this->source = other.source;
		this->offset = other.offset;
		this->rank[0] = other.rank[0];
		this->rank[1] = other.rank[1];
		return *this;
	}
	
	void print(){
		std::cout <<std::setw(3) <<rank[0] <<' ' <<std::setw(3) <<rank[1] <<' ' <<std::setw(3) <<rank[2] <<' '  <<std::setw(3) <<rank[3] <<' ' <<source.substr(offset) <<'\n';
	}
	
	void updateRank(Prefix * prev, int round){
		int first = (round*2 - 2) & 3;
		int second = (round*2 - 1) & 3;
		int next = (round*2 & 3);
		if(this->rank[first] == prev->rank[first] && this->rank[second] == prev->rank[second]){
			this->rank[next] = prev->rank[next];
		} else {
			this->rank[next] = prev->rank[next] + 1;
		}
	}
	
	void updatePrefixRank(std::vector<Prefix *> prefixes, int round) {
		int length = 1 << (round);
		int future = (round*2 + 1) & 3;
		int now = (round*2)&3;
		if(offset + length < source.length()) {
			this->rank[future] = prefixes[offset + length]->rank[now];
		} else {
			this->rank[future] = -1;
		}
	}
	
	bool compare(Prefix * other, int round){
		int first = (round*2 - 2) & 3;
		int second = (round*2 - 1) & 3;
		if(this->rank[first] == other->rank[first]){
			return this->rank[second] < other->rank[second];
		} else {
			return this->rank[first] < other->rank[first];
		}
	}
};

void compute_round(std::vector<Prefix *> &prefixes, std::vector<Prefix *> &sorted, int round){
	std::sort(sorted.begin(), sorted.end(), [round](Prefix * a, Prefix * b) {
		return a->compare(b, round);
	});
	for(auto & prefix: sorted){
		prefix->print();
	}
	std::string x;
	Prefix guard(x, 0);
	guard.rank[0] = -1;
	guard.rank[1] = -1;
	guard.rank[2] = -1;
	Prefix * prev = &guard;
	for(std::vector<Prefix *>::iterator iter = sorted.begin(); iter != sorted.end(); ++iter){
		(*iter)->updateRank(prev, round);
		prev = *iter;
	}
	for(auto & prefix: sorted){
		prefix->print();
	}
	for(auto & prefix: sorted){
		prefix->updatePrefixRank(prefixes, round);
	}
	for(auto & prefix: sorted){
		prefix->print();
	}
}

void compute_suffix(std::string &subject){
	std::vector<Prefix *> prefixes;
	std::vector<Prefix *> sorted;
	for(int i = 0; i < subject.length(); ++i){
		Prefix * prefix = new Prefix(subject, i);
		prefixes.push_back(prefix);
		sorted.push_back(prefix);
	}
	for(auto & prefix: prefixes){
		prefix->print();
	}
	int round = 1;
	while(subject.length() > (1<<round)){		
		std::cout <<"Round "<<round <<std::endl;
		compute_round(prefixes, sorted, round);
		round++;
	}
}

int main(){
	std::string subject;
	std::getline(std::cin, subject);
	compute_suffix(subject);
	std::cout <<subject<<std::endl;
}