// this is a simple C code for Algorithm 2 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 #include #include int N; // length of the input string #define null -1 void algorithm2(int* LSA,char* x); void ba(int* B,char* x); int* compute_LSA(char* x); #define _debug // these macros are only usde for debugging #define ShowInd() {printf(" ");for (int _i=0;_i 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 algorithm2(LSA,x); #ifdef _debug ShowLSA(); #endif return 0; }//end main // function algorithm2 ----------------------------------------------------- void algorithm2(int* LSA,char* x) { int* Next=(int*) malloc(N*sizeof(int)); int start; // start of the Next list int prev; // "pointer" to previous node of list Next int cur; // "pointer" to current node of list Next int* B; // will become B[] int i, j; // auxiliary variables // transform LSA to Next start=LSA[0]; for(i=0;i