Comparer les chaînes avec un caractère générique

En C, comment puis-je comparer une chaîne contenant * (qui peut être une combinaison de caractères) avec une masortingce de chaînes à deux dimensions?

Par exemple, j’ai le mot go*s . Il peut générer les mots “magnifique” ( * est “orgeou”), “bonté”, “chèvres”, “va” etc. Je suis censé lire les mots d’un dictionnaire entier et les comparer avec un mot qui en contient un ou plus d’astérisques ( * ). Chaque mot pouvant être généré à partir du mot avec l’astérisque devra être imprimé. Si les deux mots ont la même longueur, il est facile de comparer car * ne peut être qu’une lettre.

 int fq(char *s1, char *s2){ int i, a=0, b=0, s=0; while (1){ if (s1[a]=='\0') break; a++; } if (strlen(s1)==strlen(s2)){ for(i=0; i<a; i++){ if (s1[i]=='*'){ b++; } if (s1[i]==s2[i]){ b++; } } } if (b==a) return 1; 

Vous pouvez assez facilement écrire une fonction récursive pour comparer une piqûre à une autre chaîne contenant un caractère générique en examinant la chaîne de modèle, caractère par caractère, et en appliquant les règles suivantes:

  • si modèle [p] == ‘\ 0’: les modèles correspondent si candidat [c] == ‘\ 0’
  • si pattern [p] == ‘*’: essayer de faire correspondre candidat [c] … candidat [c + n] avec pattern [p + 1]
  • si motif [p]! = ‘?’ et motif [p]! = candidat [c]: pas de correspondance
  • sinon, faire correspondre le modèle [p + 1] avec le candidat [c + 1]

Ces quelques règles peuvent facilement être écrites comme une fonction récursive pour l’appariement:

 #include  bool match(const char *pattern, const char *candidate, int p, int c) { if (pattern[p] == '\0') { return candidate[c] == '\0'; } else if (pattern[p] == '*') { for (; candidate[c] != '\0'; c++) { if (match(pattern, candidate, p+1, c)) return true; } return match(pattern, candidate, p+1, c); } else if (pattern[p] != '?' && pattern[p] != candidate[c]) { return false; } else { return match(pattern, candidate, p+1, c+1); } } 

alors, vous pouvez faire:

 match("f*o", "foo", 0, 0); 

Ce n’est pas une méthode efficace, mais je pense que c’est facile à comprendre et à mettre en œuvre. Si vous avez besoin de quelque chose de plus efficace, vous pouvez commencer par ceci: http://en.wikipedia.org/wiki/Ssortingng_searching_algorithm

Ce qui suit fonctionnera avec une chaîne d’entrée contenant un seul * .

  1. Commencez à comparer un caractère à la fois au début de votre mot de saisie.
  2. Si vous rencontrez un * , comparez les deux chaînes du dernier caractère, à l’envers.
  3. Lorsque vous avez une non-correspondance, retournez 0
  4. Si vous rencontrez le * vous avez terminé.
  5. Sur un non-match, retourne 0 .

(Ajouter: Cet algorithme fonctionnerait également avec le * dans la toute première ou la dernière position.)

Vous pouvez vérifier si les deux premiers caractères sont “go” et si le dernier est “s”.

La façon la plus simple de procéder est la suivante:

 if (strncmp(str, "go", 2) == 0 && str[strlen(str) - 1] == 's') 

strncmp renvoie 0 si les chaînes correspondent.

Vous devez également vous assurer que la chaîne a au moins 2 caractères, sinon vous aurez une erreur de segmentation lorsque vous comparez 2 caractères de votre chaîne, vous pouvez append la condition ci-dessus:

 strlen(str) >= 2