Recherche d'un motif

Caractères et chaînes de caractères · niveau 3 (difficile)

Énoncé

Écrire contient s m qui teste si la chaîne m (le motif) apparaît dans s, par recherche naïve.

Corrigé

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 $Θ (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.

Énoncé

Corrigé

Exercices semblables