← Back to branch summary

~ubuntu-branches/ubuntu/hardy/ocaml-doc/hardy

« back to all changes in this revision

Viewing changes to examples/basics/kmp.ml

  • Committer: Bazaar Package Importer
  • Author(s): Samuel Mimram
  • Date: 2007-09-08 01:49:22 UTC
  • mfrom: (0.1.3 upstream)
  • Revision ID: james.westby@ubuntu.com-20070908014922-lvihyehz0ndq7suu
Tags: 3.10-1
* New upstream release.
* Removed camlp4 documentation since it is not up-to-date.
* Updated to standards version 3.7.2, no changes needed.
* Updated my email address.

Show diffs side-by-side

added added

removed removed

Lines of Context:
examples/basics/kmp.ml
1
 
(***********************************************************************)
2
 
(*                                                                     *)
3
 
(*                           Objective Caml                            *)
4
 
(*                                                                     *)
5
 
(*               Pierre Weis, projet Cristal, INRIA Rocquencourt       *)
6
 
(*                                                                     *)
7
 
(*  Copyright 2001 Institut National de Recherche en Informatique et   *)
8
 
(*  en Automatique.  All rights reserved.  This file is distributed    *)
9
 
(*  only by permission.                                                *)
10
 
(*                                                                     *)
11
 
(***********************************************************************)
12
 
 
13
 
(* Find the first occurrence of string [p] (the so-called ``pattern'')
14
 
   into the string [s].
15
 
   Elaborated algorithm.
16
 
   Knuth-Morris-Pratt algorithm following Sedgewick's book "Algorithms".
17
 
   The Caml code was proved correct in the Coq Proof Assistant.
18
 
   Based on a mail to the Caml list by Jean-Christophe FILLIATRE. *)
19
 
 
20
 
let init_next p =
21
 
  let m = String.length p in
22
 
  let next = Array.create m 0 in
23
 
  let i = ref 1 and j = ref 0 in
24
 
  while !i < m - 1 do
25
 
    if p.[!i] = p.[!j] then begin incr i; incr j; next.(!i) <- !j end else
26
 
    if !j = 0 then begin incr i; next.(!i) <- 0 end else j := next.(!j)
27
 
  done;
28
 
  next;;
29
 
 
30
 
let kmp p =
31
 
  let next = init_next p
32
 
  and m = String.length p in
33
 
  function s ->
34
 
    let n = String.length s
35
 
    and i = ref 0
36
 
    and j = ref 0 in
37
 
    while !j < m && !i < n do
38
 
      if s.[!i] = p.[!j] then begin incr i; incr j end else
39
 
      if !j = 0 then incr i else j := next.(!j)
40
 
    done;
41
 
    if !j >= m then !i - m else raise Not_found;;
42
 
 
43
 
let find_pat p s =
44
 
  try
45
 
    let i = kmp p s in
46
 
    print_string "Match found at character ";
47
 
    print_int i;
48
 
    print_newline ();
49
 
    exit 0
50
 
  with Not_found ->
51
 
    print_string "Pattern ";
52
 
    print_string p;
53
 
    print_string " does not match string ";
54
 
    print_string s;
55
 
    print_newline ();
56
 
    exit 2;;
57
 
 
58
 
let usage () =
59
 
  print_string
60
 
   "Usage: kmp <pat> <str>\n\
61
 
    returns the index of the first occurrence of <pat> in string <str>\n";
62
 
  exit 2;;
63
 
 
64
 
let main () =
65
 
  let args = Sys.argv in
66
 
  if Array.length args < 2 then usage () else
67
 
   let p = Sys.argv.(1)
68
 
   and s = Sys.argv.(2) in
69
 
  find_pat p s;;
70
 
 
71
 
if !Sys.interactive then () else main ();;