Discussion :

[saturn1]

Bonjour je cherche à créer un algorithme qui permet de compter le nombre de fois que deux chaine sont identiques.

La chaine 1 sera par exemple "hello" et la chaine 2 pour elle seule contenir des * (qui correspont à n'importe quelle chaine même vide)
Donc si str1 = abc et str2 = a**.

Il y a 3 possibiltés :
*(1) = bc et *(2) = rien
ou
*(2) = bc et *(1) = rien
ou
*(1) = b et *(2) = c

Si vous pouviez m'aider un peu pour démarrer ...

Merci

[10_GOTO_10]

Est-ce que les * sont forcément à la fin ?

Parce que sinon ça augmente la complexité du problème: par exemple si on a:
Str1=abbbc
Str2=a*b*c
Ca augmente les possibilités. Et dans ce cas ce serait un peu le principe des expressions régulières.

[saturn1]

yop, oui les * sont n'importe ou ... :s

je n'arrive pas à écrire un algo viable !

[souviron34]

• Primo tu fais un algo de recherche de sous-chaînes dans une chaîne
  
  
• Secondo, tu explores ta seconde chaîne et tu la découpes en fonction des * trouvées :
  
  a*toto*
  
  donnera [a] et [toto]
  
  
• Tertio, tu explores la chaîne 1. Si il n'y a pas de chaîne 2-1 ([a]), c'est fini. Si il y en a, tu regardes jusqu'à l'espace suivant si tu as la chaîne 2-2 ([toto]). Si il n'y en a pas, on passe au "a" suivant l'espace. Sinon on a un résultat..

[saturn1]

Ok je comprend ta réponse jusqu' à

Tertio, tu explores la chaîne 1. Si il n'y a pas de chaîne 2-1 ([a]), c'est fini...

La chaine 1 c'est la chaine qui ne contient pas de *.
Mais après "chaine 2-1 ([a])" ça veut dire quoi ???

Merci de ta réponse

[souviron34]

la chaîne 2, celle qui contient les *, j'ai mentionné au dessus que tu l'a découpée en N sous-chaînes, que j'ai appelées chaîne 2-1, 2-2, 2-3, ...

Exemple :

chaîne 1 "abc add altitude addition abécédaire"

• 1er exemple :
  
  chaîne 2 : "a*"
  
  chaine 2-1 : "a"
  résultats (5) : "abc" "add" "altitude" "addition" "abécédaire"
  
  
• 2ième exemple :
  
  chaîne 2 : "a*d*"
  
  chaîne 2-1 : "a"
  chaine 2-2 : "d"
  
  Résultats pour chaine2-1 -> on cherche chaine 2-2 -> résultat
  
  abc -> rien
  add -> "add"
  altitude -> rien
  addition -> "addition"
  abécédaire -> "abécédaire"
  
  
• 3ième exemple :
  
  
  chaîne 2 : "a*dd*"
  
  chaîne 2-1 : "a"
  chaine 2-2 : "dd"
  
  Résultats pour chaine2-1 -> on cherche chaine 2-2 -> résultat
  
  abc -> rien
  add -> "add"
  altitude -> rien
  addition -> "addition"
  abécédaire -> rien
  
  
• 4ième exemple :
  
  
  chaîne 2 : "a*e"
  
  chaîne 2-1 : "a"
  chaine 2-2 : "e" (en fin de mot)
  
  Résultats pour chaine2-1 -> on cherche chaine 2-2 -> résultat
  
  abc -> rien
  add -> rien
  altitude -> "altitude"
  addition -> rien
  abécédaire -> "abécédaire"
  
  
• 5ième exemple :
  
  
  chaîne 2 : "a*é"
  
  chaîne 2-1 : "a"
  chaine 2-2 : "é" (en fin de mot)
  
  Résultats pour chaine2-1 -> on cherche chaine 2-2 -> résultat
  
  abc -> rien
  add -> rien
  altitude -> rien
  addition -> rien
  abécédaire -> rien
  
  
• 6ième exemple :
  
  
  chaîne 2 : "a*é*"
  
  chaîne 2-1 : "a"
  chaine 2-2 : "é"
  
  Résultats pour chaine2-1 -> on cherche chaine 2-2 -> résultat
  
  abc -> rien
  add -> rien
  altitude -> rien
  addition -> rien
  abécédaire -> "abécédaire"