Au secours, recherche de caractères

[Nity26]

Bonjour tout le monde, il se trouve que je rencontre un petit problème dans l'écriture d'un algorithme caml.

J'essaye de traduire en langage caml l'algorithme explicité en page 2 de la pièce jointe. En fait, je dois parvenir à repérer l'apparition d'une chaîne de caractères dans un texte. On compare la première lettre du mot M aux lettres composant le texte T. Si les deux lettre correspondent, on compare la deuxieme lettre de M a la lettre suivante dans T.

Donc j'ai écrit cet algorithme :

# let matchnaif m t =
let lm = String.length m in
let lt = String.length t in
for i = 1 to (lt-lm+1) do let k=ref 1 in
while m.(k) = t.(k+i-1) do
if k=lm then i
else k:=!k+1 ;end ; end;;

Je n'arrive pas à le faire fonctionner, j'ai tout essayé. J'imagine que le problème se trouve dans les trois end finaux, mais je ne trouve pas la solution.
Est-ce-que quelqu'un aurait une idée ?
Cordialement

[gasche]

L'accès dans une chaîne c'est t.[i] et pas t.(i), et pour les boucles c'est do ... done et pas do .. end.

[Nity26]

merci ! je vais essayer avec ça

Après correction j'obtiens ceci :

Code :

1
2
3
4
5
6
7
8
9
10
# let matchnaif m t =
     let lm = String.length m in
     let lt = String.length t in
     let k = ref 1 in
  	for i =1 to (lt-lm+1) do
  	   k:=1;
  	   while m.[k]=t.[k+i-1] do
  		if k=lm then print_int(i)
  		else k:=!k+1
done; done;;

Et je reçois ce message d'erreur :

Code :

1
2
3
4
5
Characters 163-164:
    	   while m.[k]=t.[k+i-1] do
                 ^
Error: This expression has type int ref
       but an expression was expected of type int

[gasche]

dans "m.[k]", l'expression "k" a le type "int ref" mais on attend quelque chose de type "int".

Tu devrais utiliser les balises de code (le dièse dans les boutons du formulaire) pour que tes messages soient plus lisibles.

[Nity26]

Existe-t-il une fonction pour que le type d'une référence devienne int ? Comme int_of_ref ?

Edit: J'ai compris, il manque des !


Edit2:

Code :

1
2
3
4
5
6
7
8
9
10
# let matchnaif m t =
     let lm = String.length m in
     let lt = String.length t in
     let k = ref 1 in
  	for i =1 to (lt-lm+1) do
  	   k:=1;
  	   while m.[!k]=t.[!k+i-1] do
  		if !k=lm then print_int(i)
  		else k:=!k+1
  done; done;;

[Nity26]

Merci ! J'obtiens enfin une signature !
Je regarde si ça fonctionne.

Edit:

Code :

Exception: Invalid_argument "index out of bounds".

Malheureusement, cela ne fonctionne toujours pas.
Je vais vérifier les bornes des boucles.

[Nity26]

Avec ce code j'obtiens la réponse attendue, merci pour ton aide !

Code :

1
2
3
4
5
6
7
8
9
10
11
# let matchnaif m t =
     let lm = String.length m in
     let lt = String.length t in
     let k = ref 0 in
  	for i =1 to (lt-lm) do
  	   k:=0;
  	   while m.[!k]=t.[!k+i-1] do
  		if !k=(lm-1) then print_int(i)
  		else k:=!k+1
  done; done; print_int(0);;
val matchnaif : string -> string -> unit = <fun>

Dernière question,si tu as le temps de me répondre : l'algorithme me renvoie le chiffre attendu lors du test, mais il l'envoie en continu sans s'arrêter, et je me retrouve avec plusieurs écrans remplis de 4. Saurais-tu où se situe le problème ?

[gasche]

Ta boucle while centrale ne met pas `k` à jour dans la branche "then", ce qui donne une boucle infinie (tu peux exécuter le programme dans ta tête pour comprendre ce qui se passe).

[prgasp77]

Bonjour à vous deux,

je me permets d'intervenir pour donner un petit conseil à l'OP : quand c'est possible, subdivise ton problème en plusieurs sous-problèmes. Quand ça ne marche pas, il est possible de localiser le dysfonctionnement et de diviser sensiblement la taille du code à débugger.

Ici, il est possible d'écrire au préalable la fonction
substring_equal: a:string -> offset_a:int -> b:string -> offset_b:int -> size:int -> bool qui se contente d'appliquer ton algorithme sur des strings de même taille. substring_equal retourne true si et seulement si les size caractères de a à l'indice offset_a égalent les size caractères de b à l'indice offset_b.

Une fois un tel outil développé et testé, rien de plus simple que de l'utiliser pour chercher un mot dans une longue chaine de caractères

Cdlt,

[Nity26]

Merci pour le tuyau.