Recherche d'un motif

let contient s m =
  let ns = String.length s and nm = String.length m in
  let trouve = ref false in
  for i = 0 to ns - nm do
    let ok = ref true in
    for j = 0 to nm - 1 do
      if s.[i + j] <> m.[j] then ok := false
    done;
    if !ok then trouve := true
  done;
  !trouve

Pour chaque position de départ i (de 0 à ns - nm), on vérifie que les nm caractères coïncident. Le coût est $\Theta (n_s\cdot n_m)$ dans le pire cas. Si m est plus longue que s, la borne ns - nm est négative et la boucle ne s'exécute pas : false, comme attendu.