Suffix Array

suffixarray.c

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

int compar(const void* a, const void* b) {
  return strcmp(*(const char**)a, *(const char**)b);
}

int main(int argc, char** argv) {
  const char *giantString =
    "Lorem ipsum dolor sit amet,"
    " consectetur adipiscing elit,"
    " sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.";

  // Creating a suffix array from the "giant" string
  const size_t size = strlen(giantString);
  const char **suffixArray = (const char**)malloc(size * sizeof(char*));
  for (int i = 0; i < size; i ++) {
    suffixArray[i] = &giantString[i];
  }
  qsort(suffixArray, size, sizeof(char*), compar);

  // Let's search a string "tempo"
  const char *key = "tempo";

  // Binary search
  const char **p1 = suffixArray;
  const char **p2 = suffixArray + size;
  while (p1 < p2 - 2) {
    const char **m = p1 + (p2 - p1) / 2;
    if (strcmp(*m, key) > 0) {
      p2 = m + 1;
    } else {
      p1 = m;
    }
  }

  printf("found: %s\n", *(p2 - 1));
}