Karkkeinen2

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
#include<time.h>

#define N (int)1e6+77
int s[N];
int n;

void input() {
	char *sp = calloc(N,sizeof(char));
	int nw = 0;
	int i;
	n = 1e6; // rozmiar slowa
	for(i=0;i<n;i++) // losowanie slowa
		sp[i] = rand()%26+'a';
	n = strlen(sp);
	int jest[150];
	for(i=0;i<150;i++) {
		jest[i] = 0;
	}
	for(i=0;i<n;i++) {
		jest[sp[i]] = 1;
	}

	int kolor[150];
	int ile = 0;
	for(i=0;i<150;i++) {
		if(jest[i])
			ile++;
		kolor[i] = ile;
	}
	for(i=0;i<n;i++) {
		s[i] = kolor[sp[i]];
	}
	free(sp);
}

struct Vector {
	 void* *arr;
	 int size;
	 int capacity;
};

typedef struct Vector Vector;

void VectorInit(Vector *x) {
	assert(x!=NULL);
	x->arr = NULL;
	x->size = 0;
	x->capacity = 0;
}

void VectorPushBack(Vector *x, void *el) {
	assert(x!=NULL);
	if(x->size + 1 > x->capacity) {
		if(x->capacity > 0) {
			x->arr = realloc(x->arr, x->capacity*2*sizeof(void*));
			x->capacity*=2;
		}
		else {
			x->arr = calloc(1,sizeof(void*));
			x->capacity=1;
		}
	}
	x->arr[x->size] = el;
	x->size++;
}

void VectorClear(Vector *x) {
	assert(x!=NULL);
	if(x->capacity > 0)
		free(x->arr);
	x->size = 0;
	x->capacity = 0;
}

struct Triple {
	int val[3];
	int who;
};

typedef struct Triple Triple;

Triple new_Triple(int a, int b, int c, int d) {
	Triple k;
	k.val[0] = a;
	k.val[1] = b;
	k.val[2] = c;
	k.who = d;
	return k;
}

inline bool rozne(Triple *x, Triple *y) {
	int i=0;
	for(i=0;i<3;i++) {
		if(x->val[i] != y->val[i])
			return true;
	}
	return false;
}

Triple* sortTriples(Triple *box, int size, int range) { // w boxie sa wspolrzedne >= 0 i <= size
	Vector vec[range];
	int i;
	for(i=0;i<range;i++)
		VectorInit(&vec[i]);
	void *wsk[size];
	for(i=0;i<size;i++)
		wsk[i] = &box[i];
	void *wskc[size+4];
	for(i=2;i>=0;i--) {
		int j;
		for(j=0;j<size;j++) {
			VectorPushBack(&vec[((Triple*)wsk[j])->val[i]],wsk[j]);
		}
		int wskcsize = 0;
		int k;
		for(j=0;j<range;j++) {
			for(k=0;k<vec[j].size;k++) {
				wskc[wskcsize++] = vec[j].arr[k];
			}
		}
		for(j=0;j<wskcsize;j++) {
			wsk[j] = wskc[j];
		}
		for(j=0;j<range;j++) {
			VectorClear(&vec[j]);
		}
	}
	Triple *res = calloc(size,sizeof(Triple));
	for(i=0;i<size;i++) {
		res[i] = *((Triple*)wsk[i]);
	}
	free(box);
	return res;
}

int compress(int *l, int **nowaw, int roz, int *ilep, bool* dorzucono) {
	int *nowa;
	int *gdzie = calloc(roz,sizeof(int));
	Triple *worek = calloc(roz,sizeof(Triple));
	int size = 0;
	int i;
	*ilep = 0;
	*dorzucono = false;
	// mod 3 = 1
	for(i=1;i+2<roz;i+=3) {
		worek[size++] = new_Triple(l[i],l[i+1],l[i+2],i);
		(*ilep)++;
	}
	if(i==roz-2) {
		worek[size++] = new_Triple(l[roz-2],l[roz-1],0,roz-2);
		(*ilep)++;
	} else if(i == roz-1) {
		worek[size++] = new_Triple(l[roz-1],0,0,roz-1);
		(*ilep)++;
	} else {
		*dorzucono = true;
	}
	// mod 3 = 2
	for(i=2;i+2<roz;i+=3) {
		worek[size++] = new_Triple(l[i],l[i+1],l[i+2],i);
	}
	if(i==roz-2) {
		worek[size++] = new_Triple(l[roz-2],l[roz-1],0,roz-2);
	} else if(i == roz-1) {
		worek[size++] = new_Triple(l[roz-1],0,0,roz-1);
	}

	Triple *temp = sortTriples(worek,size,roz+1);
	worek = temp;

	int nic = 1;
	for(i=0;i<size;i++) {
		if(i>0 && rozne(&worek[i],&worek[i-1])) {
			nic++;
		}

		gdzie[worek[i].who] = nic;
	}

	int nowasize = 0;
	nowa = calloc(size+1,sizeof(int));
	*nowaw = nowa;
	// mod 3 = 1
	for(i=1;i+2<roz;i+=3) {
		nowa[nowasize++] = gdzie[i];
	}
	if(i==roz-2) {
		nowa[nowasize++] = gdzie[roz-2];
	} else if(i == roz-1) {
		nowa[nowasize++] = gdzie[roz-1];
	}

	// dodawanie $
	if(*dorzucono)
		nowa[nowasize++] = 0;

	// mod 3 = 2
	for(i=2;i+2<roz;i+=3) {
		nowa[nowasize++] = gdzie[i];
	}
	if(i==roz-2) {
		nowa[nowasize++] = gdzie[roz-2];
	} else if(i == roz-1) {
		nowa[nowasize++] = gdzie[roz-1];
	}
	free(gdzie);
	free(worek);
	return nowasize;
}

struct Pair {
	int a[2];
};

typedef struct Pair Pair;

Pair newPair(int d, int e) {
	Pair x;
	x.a[0] = d;
	x.a[1] = e;
	return x;
}


int* count_sa(int *l, int roz) {
	int i;
	if(roz==1) {
		int *x = calloc(1,sizeof(int));
		x[0] = 0;
		return x;
	}
	int *nowa;
	int ilep;
	bool dorzucono;
	int dorz;
	int nowasize = compress(l,&nowa,roz,&ilep,&dorzucono);
	if(dorzucono)
		dorz = 1;
	else
		dorz = 0;
	int *sa_old = count_sa(nowa,nowasize); // tablica Sufiksowa dla 1 i 2 mod 3
	int *rank = calloc(roz+1,sizeof(int)); // tablica RANK
	int lol = 1;
	for(i=0;i<nowasize;i++) {
		if(sa_old[i] < ilep)
			rank[sa_old[i]*3+1] = lol++;
		else  if(sa_old[i] > ilep || (sa_old[i] == ilep && !dorzucono)) {
			rank[(sa_old[i]-ilep-dorz)*3+2] = lol++;
		}
	}

	free(nowa);
	int wsk = 1;

	Pair pary[roz/3+6]; // pary gosci podzielnych przez 3
	for(i=0;i<roz;i+=3) {
		if(i+1<roz)
			pary[i/3] = newPair(l[i],rank[i+1]);
		else
			pary[i/3] = newPair(l[i],0);
	}

	int j;
	Vector wor;
	VectorInit(&wor);
	for(i=0;i<roz;i+=3) {
		VectorPushBack(&wor,(void*)&pary[i/3]);
	}
	Vector buckets[roz+5];
	for(j=roz+4;j>=0;j--)
		VectorInit(&buckets[j]);
	int t;
	for(j=1;j>=0;j--) {
		for(t=0;t<wor.size;t++) {
			VectorPushBack(&buckets[((Pair*)wor.arr[t])->a[j]],wor.arr[t]);
		}
		void* wskaznik[wor.size+1];
		int wskazniksize = 0;
		for(t=0;t<=roz+4;t++) {
			for(i=0;i<buckets[t].size;i++) {
				wskaznik[wskazniksize++] = buckets[t].arr[i];
			}
		}
		for(t=0;t<wskazniksize;t++) {
			wor.arr[t] = wskaznik[t];
		}
		for(t=0;t<roz+5;t++)
			VectorClear(&buckets[t]);
	}
	int* zerowe  = calloc(roz/3+4,sizeof(int));
	int zerowesize = 0;
	for(i=0;i<wor.size;i++) {
		zerowe[zerowesize++] = (((Pair*)wor.arr[i])-pary)*3;
	}
	VectorClear(&wor);
	// zmerguj
	int* saRes = calloc(roz,sizeof(int));
	int saRessize = 0;
	int* niezerowe = calloc(roz/3*2+4,sizeof(int));
	int  niezerowesize = 0;
	wsk = 0;
	for(i=0;i<nowasize;i++) {
		if(!(dorzucono && sa_old[i] == ilep)) {
			if(sa_old[i] < ilep) {
				niezerowe[niezerowesize++] = sa_old[i]*3+1;
			} else {
				niezerowe[niezerowesize++] = (sa_old[i]-ilep-dorz)*3+2;
			}
		}
		wsk++;
	}
	free(sa_old);
	i = 0, j = 0;
	while( i < zerowesize || j < niezerowesize) {
		if( j == niezerowesize) {
			saRes[saRessize++] = zerowe[i++];
		} else if( i == zerowesize) {
			saRes[saRessize++] = niezerowe[j++];
		} else {
			if(l[niezerowe[j]] == l[zerowe[i]]) {
				if(niezerowe[j]%3==1) {
					if(rank[niezerowe[j]+1] < rank[zerowe[i]+1])
						saRes[saRessize++] = niezerowe[j++];
					else
						saRes[saRessize++] = zerowe[i++];
				} else {
					if(niezerowe[j]+1 >= roz) {
						saRes[saRessize++] = niezerowe[j++];
					} else if(zerowe[i]+1 >= roz) {
						saRes[saRessize++] = zerowe[i++];
					} else {
						if(l[niezerowe[j]+1] == l[zerowe[i]+1]) {
							if(rank[niezerowe[j]+2] < rank[zerowe[i]+2])
								saRes[saRessize++] = niezerowe[j++];
							else
								saRes[saRessize++] = zerowe[i++];
						}  else {
							if(l[niezerowe[j]+1] < l[zerowe[i]+1])
								saRes[saRessize++] = niezerowe[j++];
							else
								saRes[saRessize++] = zerowe[i++];
						}
					}
				}
			}
			else {
				if(l[niezerowe[j]] < l[zerowe[i]]) {
					saRes[saRessize++] = niezerowe[j++];
				} else {
					saRes[saRessize++] = zerowe[i++];
				}
			}
		}
	}
	free(zerowe);
	free(niezerowe);
	free(rank);

	return saRes;
}


int main () {
	input();
	int *res = count_sa(s,n);

	//printf("SA : \n");
	int i;
	for(i=0;i<n;i++) {
		printf("%d ", res[i]);
	}
	free(res);
	return 0;
}