Kody 1

OCAML - Kody użytecznych rzeczy

(* NWD *)
let rec nwd a b =
    if b = 0 then a else gcd b (a mod b);;

(* NWW *)
let nww a b = (a*b)/(nwd a b);;



(** Binsearch + KMP, credits - Marcin Kurowski **)

(* pierwsza potega 2 wieksza od x *)
let rec pot x wyn =
  if x > 0
  then pot (x/2) wyn*2
  else wyn

(* znajduje indeks ostatniej liczby mniejszej badz rownej x *)
let binsearch tab x =
  let pocz = ref (-1) in
  let ws = ref (pot (length tab) 1) in
  while !ws != 0 do
    let sr = ((!pocz) + (!ws)) in
    if sr < (length tab) && tab.(sr) <= x
    then (
      pocz := sr;
      ws := (!ws) / 2
      )
    else ws := (!ws) / 2
  done;
  !pocz;;

(* znajduje indeks ostatniej liczby mniejszej od x *)
  let binsearch_mn tab x =
  let pocz = ref (-1) in
  let ws = ref (pot (length tab) 1) in
  while !ws != 0 do
  let sr = ((!pocz) + (!ws)) in
  if sr < (length tab) && tab.(sr) < x
  then (
    pocz := sr;
    ws := (!ws) / 2
    )
    else ws := (!ws) / 2
  done;
  !pocz;;


(*KMP Credits Marcin Kurowski*)

open Array

let kmp slowo wzorzec =
  let calosc = make ((length slowo) + (length wzorzec) + 5) "" in
  for i = 0 to (length wzorzec) - 1 do
    calosc.(i) <- wzorzec.(i)
  done;
  for i = (length wzorzec) + 1 to (length wzorzec) + (length slowo) do
    calosc.(i) <- slowo.(i - (length wzorzec) - 1)
  done;
  calosc.(length wzorzec) <- "#";
  let dl = (length wzorzec) + (length slowo) + 1 in
  let odp = make (dl) 0 in
  for i = 1 to (dl - 1) do
    if calosc.(odp.(i-1)) = calosc.(i)
    then odp.(i) <- odp.(i-1) + 1
    else (
        let k = ref odp.(i-1) in
        let ok = ref 1 in
        while !k != (-1) && !ok = 1 do
          if calosc.(i) = calosc.(!k)
          then (
            odp.(i) <- (!k) + 1;
            ok := 0;
          );
          (if !k = 0 then ok := 0);
          k := odp.(!k);
        done
      )
  done;
  odp;;