let p = 997
let q = 1000000007

let potegi = Array.make 1000005 0;;
begin
  potegi.(0) <- 1;
  for i = 1 to 1000000 do
    potegi.(i) <- (potegi.(i-1) * p) mod q;
  done
end

let hasze = (Array.make 1000000 0)
let dlugosc = ref 0

let licz_hasze slowo = begin
  dlugosc := Array.length slowo;
  hasze.(0) <- Char.code slowo.(0);
  for i = 1 to !dlugosc - 1 do
    hasze.(i) <- (hasze.(i - 1) * p + Char.code slowo.(i)) mod q;
  done;
end

let hasz_wzorca wzorzec =
  let wyn = ref (Char.code wzorzec.(0)) in
  let len = Array.length wzorzec in
  for i = 1 to len - 1 do
    wyn := (!wyn * p + Char.code wzorzec.(i)) mod q;
  done;
  !wyn

let hasz_przedzialu i j =
  if i = 0 then hasze.(j)
  else (q + hasze.(j) - (hasze.(i - 1) * potegi.(j - i + 1)) mod q) mod q;;

let licz_wzorce wzorzec =
  let wzorzec_hasz = hasz_wzorca wzorzec in
  let i = ref 0 in
  let j = ref (Array.length wzorzec - 1) in
  let wynik = ref 0 in
  while !j <= !dlugosc - 1 do
    (if hasz_przedzialu !i !j = wzorzec_hasz then wynik := !wynik + 1
    else ());
    i := !i + 1;
    j := !j + 1;
  done;
  !wynik;;