// this is a simple C code for Algorithm 1 of the paper 
// "Reconstructing a suffix array"

// note that for the suffix array and the input string x we use C indexing 
// starting from 0 rather than the more common indexing used in the paper
// starting from 1
// Therefore we cannot use 0 in the usual meaning, and hence introduce a
// special symbol null

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int N;   // length of the input string
#define null -1


void algorithm1(int* LSA,char* x);
void ba(int* B,char* x);
int* compute_LSA(char* x);


// #define _debug
// uncomment the above line and recompile for debugging

// these macros are only use for debugging
// in displays, the dot indicates the value null
#define ShowInd() {printf("      ");for (int _i=0;_i<N;_i++)\
     printf("%2d ",_i);putchar('\n');fflush(stdout);}
#define ShowLSA() {printf("LSA  :");\
     for(int _i=0;_i<N;_i++) \
        if (LSA[_i]==null) \
      printf("   "); \
        else \
      printf("%2d ",LSA[_i]);putchar('\n');fflush(stdout);}
#define ShowB() {printf("B    :"); \
     for(int _i=0;_i<N;_i++) \
    if (B[_i]==null) \
      printf(" . "); \
    else \
      printf("%2d ",B[_i]);putchar('\n');fflush(stdout);}
#define ShowNext() {printf("Next:  "); \
     for(int _i=0;_i<N;_i++) \
        if (Next[_i]==null) \
            printf("   "); \
        else \
            printf("%2d ",Next[_i]);putchar('\n');fflush(stdout);}
#define ShowString(){ \
	printf("x    : "); \
       	for(int _i=0;_i<N;_i++) \
       	  printf("%c  ",x[_i]); \
        putchar('\n');fflush(stdout);}
#define TraverseNext() { \
	printf("Trav: "); \
        int _i=start; \
	while(_i!=null){ \
		printf("%2d ",_i);_i=Next[_i];} \
	putchar('\n');fflush(stdout);}


// create and compute the suffix array of the input string
// function compute_LSA ------------------------------------------------------
int* compute_LSA(char* x)
{  
  int* LSA=(int*) malloc(N*sizeof(int)); // allocate memory
  // the following code must be replaced by the actual computation of 
  // the suffix array of the input string rather than the following
  // suffix array for the sample input string "abcaabcdabccabdabea"
  
  int i=0;
  LSA[i++]=18; LSA[i++]=3; LSA[i++]=0; LSA[i++]=8; LSA[i++]=4;
  LSA[i++]=12; LSA[i++]=15; LSA[i++]=1; LSA[i++]=9; LSA[i++]=5;
  LSA[i++]=13; LSA[i++]=16; LSA[i++]=2; LSA[i++]=11; LSA[i++]=10;
  LSA[i++]=6; LSA[i++]=7; LSA[i++]=14; LSA[i++]=17; 
  return LSA;
}// end compute_LSA



// compute beta array
// fill in B, assumed to be at least of length N, no memory allocated
// B[i]=null iff x[i..N-1] does not have border
// B[i]=j iff x[j..N-1] is the longest border of x[i..N-1]
// function ba ---------------------------------------------------------------
void ba(int* B,char *x)
{
  int i,c;
  int N_1=N-1;  // precompute N-1
  int N_2=N-2;  // precomuute N-2
  
  B[N_1]=null;  
  for (i=0; i < N_1; i++) {
    c = ((B[N_1-i]==null)?(0):(N-B[N_1-i]));
    while (c > 0 && x[N_2-i] != x[N_1-c])
      c =((B[N-c]==null)?(0):(N-B[N-c]));
    if (x[N_2-i] == x[N_1-c])
      B[N_2-i] = N_1-c;
    else
      B[N_2-i] = null;
  }
}//end ba




// function main ------------------------------------------------------------
int main()
{
  char x[]="abcaabcdabccabdabea";   // sample input string
  N=strlen(x);

#ifdef _debug
  ShowInd();
  ShowString();
#endif

  int* LSA = compute_LSA(x);
#ifdef _debug
  ShowLSA();
#endif

  algorithm1(LSA,x);

#ifdef _debug
  ShowLSA();
#endif

  return 0;
}//end main



// function algorithm1 -----------------------------------------------------
void algorithm1(int* LSA,char* x)
{
  int* Next = (int*) malloc(N*sizeof(int));
  int* B = (int*) malloc(N*sizeof(int));
  int start;
  int i, j, k;
  
  ba(B,x);  // compute values for B
#ifdef _debug
  ShowB();
#endif

  start=LSA[0];
  for(i=1;i<N;i++) {
    j=LSA[i];
    if (B[j]==null) {   // j goes to the front
      Next[j]=start;
      start=j;
    }else{              // j goes behind B[j]
      k=Next[B[j]];
      Next[B[j]]=j;
      Next[j]=k;
    }
  }


  // transform Next to LSA
  for(i=0,j=start;i<N;i++,j=Next[j])
    LSA[i]=j;
}//end algorithm1