let mod_p = 1000003
let base = 257

let rolling_match text pat =
  let n = String.length text in
  let m = String.length pat in
  if m > n then 0
  else begin
    let pat_hash = ref 0 in
    let win_hash = ref 0 in
    let high = ref 1 in
    for _ = 0 to m - 2 do
      high := (!high * base) mod mod_p
    done;
    for i = 0 to m - 1 do
      pat_hash := (!pat_hash * base + Char.code pat.[i]) mod mod_p;
      win_hash := (!win_hash * base + Char.code text.[i]) mod mod_p
    done;
    let count = ref 0 in
    for i = 0 to n - m do
      if !win_hash = !pat_hash then begin
        let ok = ref true in
        for j = 0 to m - 1 do
          if text.[i + j] <> pat.[j] then ok := false
        done;
        if !ok then count := !count + 1
      end;
      if i < n - m then begin
        let drop = (Char.code text.[i] * !high) mod mod_p in
        win_hash := ((!win_hash - drop + mod_p) * base + Char.code text.[i + m]) mod mod_p
      end
    done;
    !count
  end

;;

rolling_match "abcabcabcabcabcabc" "abc"
