#include <stdio.h>

#define Corpus "to be or not to be"

char *corpus;
int  N;
int  *s;
int  *lcp;

int suffix_compare(int *a, int *b){
    return strcmp(corpus+*a, corpus+*b);
}

int complcp(int i, int *sarray){
    int j;
    for(j = 0; corpus[sarray[i]+j] == corpus[sarray[i-1]+j]; j++);
    return j;
}

int *suffix_array(char *cor){
    int *sarray = (int *)malloc(sizeof(int) * N);
    int i;
    for(i = 0; i < N; i++) sarray[i] = i;
    qsort(sarray, N, sizeof(int), suffix_compare);
    return sarray;
}

int *lcp_array(int *sarray){
    int *lcparray = (int *)malloc(sizeof(int) * N + 1);
    int i;
    for(i = 1; i < N; i++) {
        lcparray[i] = complcp(i, sarray);
    }
    lcparray[0] = lcparray[N] = 0;
    return lcparray;
}

void output(int i, int j, int k){
    int LBL = (lcp[i] > lcp[j+1]) ? lcp[i] : lcp[j+1];
    int SIL = lcp[k];
    if(i==j) printf("trivial <%d,%d>, tf=1\n", i, j);
    else if(LBL < SIL) printf("nontrival <%d, %d>, rep=%d, tf=%d\n",
                              i, j, k, j-i+1);
}

int print_LDIs(int i, int k){
    int j = k;
    output(k,k,0); /* trivial intervals */
    while(lcp[k] <= lcp[j+1] && j+1 < N) j = print_LDIs(k, j+1);
    output(i,j,k); /* non-trivial intervals */
    return j;
}

#define STACK_SIZE 100000
#define Top_i (stack[sp-1].i)
#define Top_k (stack[sp-1].k)

struct STACK {int i; int k;} stack[STACK_SIZE];
int  sp = 0; /* stack pointer */

void push(int i, int k) {
    if(sp >= STACK_SIZE) {
        fprintf(stderr, "stack overflow\n");
        exit(2);}
    stack[sp].i = i;
    stack[sp++].k = k;
}

void pop() {sp--;}

void print_LDIs_stack(int N) {
    int j;
    push(0,0);
    for(j = 0; j < N; j++) {
        output(j, j, 0);
        while(lcp[j+1] < lcp[Top_k]) {
            output(Top_i, j, Top_k);
            pop();
        }
/* original code */
        push(Top_k, j+1);

/* efficient code */
/*
        if(lcp[Top_k] == lcp[j+1]) Top_k = j+1;
        else push(Top_k, j+1);
*/
    }
}

main(){
    int i;
    corpus = Corpus;
    N = strlen(corpus);
    s = suffix_array(corpus);
    printf("     i = ");
    for(i = 0; i < N; i++) printf("%2d ", i);
    printf("\n");
    printf("cor[i] = ");
    for(i = 0; i < N; i++) printf(" %c ", corpus[i]);
    printf("\n");
    printf("s[i]   = ");
    for(i = 0; i < N; i++) printf("%2d ", s[i]);
    printf("\n");
    lcp = lcp_array(s);
    printf("lcp[i] = ");
    for(i = 0; i < N+1; i++) printf("%2d ", lcp[i]);
    printf("\n");

/* recursive version */
    print_LDIs(0, 0);

/* own stack version */
/*
    print_LDIs_stack(N);
*/
}