Algo de Pattern matching

Bonjour a tous,

Je cherche un algorithme qui me permettrait de faire matcher des chaines, j'etend par la de les comparer tout en introduisant un caractere joker

exemple : Test et T*st match ou Test et Test* match aussi

Je pensais diviser selon 3 cas, suivant la longueur de la chaine pattern :

- Si les deux chaines font la meme taille, comparer lettre par lettre
- Si le pattern est plus petit, aligner le pattern sur la premiere lettre qui match et remplir le reste avec des * et me ramener au cas 1
- Si le pattern est plus grand ? Je ne sais pas :)

Auriez-vous un algo ?

Merci.

Que veux tu dire par "comparer" ? Calculer la distance entre les 2 chaines ?

Dire si elles sont identique a un joker pret ;)

Exemple : "test" et "test" sont identique, "t*" et "test" aussi

ah... du Wildcard matching. Et bien il y a plein d'algorithmes. Par exemple ici.

Aucun de ces exemples n'est complet, il manque le tableau mapCaseTable a chaque fois :/

Citation:

---

Envoyé par iowa

Aucun de ces exemples n'est complet, il manque le tableau mapCaseTable a chaque fois :/

---

:D

C'est un vieil héritage du DOS : DosMapCase.

C'est une table de conversion qui transforme les 256 codes ASCII possibles (0...255) en caractères lisibles, de meme casse et sans accents. Ca permet de faire rapidement des comparaisons qui gèrent tous les cas de caractères équivalents.

...
mapCaseTable['e']='E'
mapCaseTable['é']='E'
mapCaseTable['è']='E'
mapCaseTable['ê']='E'
...

Dans un premier temps, tu peux simplement créer une table de conversion qui ne convertit rien. ;)

CHAR mapCaseTable[256];
for (i = 0; i < 256; ++i) mapCaseTable[i] = i;

Super, ca fonctionne, tu penses que pour compter le nombre de fois que le pattern matche avec la string a comparer le raisonnement est similaire ?

Citation:

---

Envoyé par iowa

Super, ca fonctionne, tu penses que pour compter le nombre de fois que le pattern matche avec la string a comparer le raisonnement est similaire ?

---

Que veux tu dire par "le nombre de fois que le pattern matche avec la string" ?

Soit le pattern correspond, soit il ne correspond pas. Mais je ne vois pas ce que vient faire le "nombre de fois".

Par exemple : abcbd et *b* matchent 2 fois : ("a","cbd") et ("abc","d")