Knuth-Morris-Pratt string search algorithm

KMP.tq

let search p =
  let m = # p in
  let next = Array.init m [_ -> 0] in
  let rec init(i, j) =
    if i >= m-1 then () else
      if Array.get p i = Array.get p j then
        let () = Array.Unsafe.set next (i+1) (j+1) in
        init(i+1, j+1)
      else
        if j=0 then init(i+1, j) else init(i, Array.get next j) in
  let () = init(1, 0) in
  [ t -> 
    let n = # t in
    let rec loop(i, j) =
      if j < m && i < n then
        if Array.get t i = Array.get p j then loop(i+1, j+1) else
          if j = 0 then loop(i+1, j) else loop(i, Array.get next j)
      else
        if j = m then Some(i - m) else None in
    loop(0, 0) ]