ojudge

A self-hosted competitive programming site written in OCaml
git clone git://git.laack.co/ojudge.git
Log | Files | Refs | README

ocaml.ml (1526B)


      1 let readString () = 
      2     Scanf.scanf " %s" (fun x->x)
      3 
      4 let stupidHash a =
      5     let rec acc idx thusFar =   
      6         if idx = (String.length a) then thusFar
      7             else acc (idx+1) (((thusFar*2 + (int_of_char a.[idx] - (int_of_char 'a'))) mod 7919))
      8     in acc 0 0
      9 
     10 let incremental running evicting adding pow =
     11     let newRunning = 
     12         (running*2 - (int_of_char evicting - int_of_char 'a')*pow + (int_of_char adding - int_of_char 'a')) mod 7919
     13     in if newRunning < 0 then newRunning + 7919 else newRunning
     14 
     15 let sumMatches a b =
     16     let hashB = stupidHash b in
     17     let pow = let rec p i x = if i = 0 then x else p (i-1) (x*2 mod 7919) in p (String.length b) 1 in
     18     let startingHash = stupidHash (String.sub a 0 (String.length b)) in
     19         let rec acc idxToAdd runningHash sum = 
     20             if idxToAdd = String.length a then sum else
     21             let newHash = incremental runningHash a.[idxToAdd - String.length b] a.[idxToAdd] pow in
     22             acc (idxToAdd+1) newHash (if newHash = hashB && String.sub a (idxToAdd - String.length b + 1) (String.length b) = b then sum+1 else sum)
     23     in acc (String.length b) startingHash (if startingHash = hashB && String.sub a 0 (String.length b) = b then 1 else 0)
     24         
     25 
     26 let () = 
     27     let a = readString () in
     28     let b = readString () in
     29     let c = readString () in
     30     let d = readString () in
     31         let ls = [a;b;c] in
     32             let sums = List.map (fun s -> sumMatches s d) ls in
     33                 print_int (List.fold_left Int.add 0 sums); print_newline ()