Karkkeinen

#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 = 1e5+2; // 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;
}