Compute the suffix array of an array

SuffixArray.tq

let suffixArray str =
  let g = Array.get in
  let n = # str in
  let sa = Array.init n id in
  let pos = Array.copy str in
  let tmp = Array.init n [_ -> 0] in
  let sufCmp gap (i, j) =
    compare (g pos i, g pos j) @
    [ Equal ->
        if i+gap >= n || j+gap >= n then compare(j, i) else
          compare (g pos (i+gap), g pos (j+gap))
    | c -> c ] in
  let rec loop gap =
    let () = Array.Unsafe.sortInPlaceWith (sufCmp gap) sa in
    let () =
      for 0 1 (n-2) () [(), i ->
        let f = [ Less -> 1 | Equal | Greater -> 0 ] in
        g tmp i + f(sufCmp gap (g sa i, g sa (i+1)))
        @ Array.Unsafe.set tmp (i+1)] in
    let () =
      for 0 1 (n-1) () [(), i ->
        g tmp i @ Array.Unsafe.set pos (g sa i)] in
    if g tmp (n-1) = n-1 then sa else loop (2*gap) in
  loop 1