Attachment 'BurrowsWheeler.c'

Download

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4 
   5 char S[30000];
   6 int I[30000];
   7 int N;
   8 
   9 int cmp_shift(const void *a, const void *b)
  10 {
  11     int i;
  12     const int *da = (const int *) a;
  13     const int *db = (const int *) b;
  14     for (i=0; i<N; i++)
  15         if(S[(i+*da)%N]-S[(i+*db)%N]) return S[(i+*da)%N]-S[(i+*db)%N];
  16     return 0;
  17 }
  18 
  19 int main(int argc, char *argv[]) {
  20     int i;
  21     scanf("%s",S);
  22     N=strlen(S);
  23     for(i=0; i<N; i++) I[i]=i;
  24     qsort(I,N,sizeof(int),cmp_shift);
  25     for(i=0; i<N; i++) printf("%c",S[(I[i]+N-1)%N]);
  26     printf("\n");
  27     return 0;
  28 }

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.