Comment dites-vous si deux caractères génériques se chevauchent?

Étant donné que chaque glob peut être écrit comme une expression régulière et que l'intersection de deux expressions régulières peut être trouvée (à moins qu'elles ne soient pas vraiment régulières, mais elles seraient dans ce cas), vous pouvez trouver l'intersection de deux globs par les transformant en expressions régulières et ensuite à trouver l'intersection de ceux-ci. Vous pouvez donc déterminer si deux globs se croisent en trouvant l'intersection des expressions régulières et en vérifiant si c'est vide.

Cependant, depuis que les globes sont plus limités que l'expression régulière, il existe un beaucoup em> moyen: P>

Appelons les deux globs G1 et G2. Ils intersectez iff p>

1. G1 et G2 sont vides ou ne contiennent que des caractères génériques. Li>
2. Ni G1 ni G2 ne sont vides et l'une des conditions suivantes est vraie (que C1 soit le premier caractère de G1 et T1 la chaîne contenant les caractères restants - même pour G2 avec C2 et T2):
   1. C1 et C2 sont égaux et T1 et T2 intersect li>
   2. C1 et / ou C2 est une glycard et T1 intersectes avec G2 LI>
   3. C1 et / ou C2 est un intersection générique et G1 avec T2 Li> ol> li> ol>

      Exemple de mise en œuvre dans HASKELLL: P>

      intersect g1          []          = all (== '*') g1
      intersect []          g2          = all (== '*') g2
      intersect g1@('*':t1) g2@(c2:t2)  = intersect g1 t2 || intersect t1 g2
      intersect g1@(c1:t1)  g2@('*':t2) = intersect t1 g2 || intersect g1 t2
      intersect    (c1:t1)     (c2:t2)  = c1 == c2        && intersect t1 t2
      

Pour ce que ça vaut la peine, voici une implémentation forte> de l'algorithme de la réponse de Sepp2k en C # (j'ai utilisé explicite retour vrai; code> et retour false; code > Appels, avec des commentaires, pour la lisibilité des algorithmes):

public static bool WildcardIntersect(string w1, string w2)
{
    // if both are empty or contain wildcards
    if ((string.IsNullOrEmpty(w1) || w1 == "*")
        && (string.IsNullOrEmpty(w2) || w2 == "*"))
        return true;

    // if either string is empty, return false
    // we can do this because we know the other string MUST be non-empty and non-wildcard
    if (string.IsNullOrEmpty(w1) || string.IsNullOrEmpty(w2))
        return false;

    char c1 = w1[0], // first character of wildcard string 1
         c2 = w2[0]; // first character of wildcard string 2
    string remain1 = w1.Substring(1), // remaining of wildcard string 1
           remain2 = w2.Substring(1); // remaining of wildcard string 2

    // if first letters match and remaining intersect
    if ((c1 == c2 && WildcardIntersect(remain1, remain2))
        // if either is a wildcard and either remaining intersects with the other whole
        || ((c1 == '*' || c2 == '*') && (WildcardIntersect(w1, remain2) || WildcardIntersect(remain1, w2))))
        return true;

    // else, no match, return false
    return false;
}

Si je comprends bien, vous essayez de déterminer si une regex est orthogonale à une autre regex? Si tel est le cas, ce n'est pas un problème trivial.

Voici plus sur Théorie.

Voici une solution: bibliothèque Java.

Utilisation: < / p> xxx

Voici une implémentation C ++ de l'algorithme suggérée par SEPP2K avec de légères modifications: xxx

Vous pouvez résoudre ce temps en temps linéaire dans la somme des longueurs de motif:

Si les deux chaînes commencent ou se terminent par des non-caractères, vérifiez qu'elles correspondent à un motif frappe un caractère générique (sinon ils ne correspondent pas). Cela réduit le problème dans le cas où au moins un motif commence par une carte générique et au moins un motif se termine par une carte générique. Si les deux motifs ont des caractères génériques (quelque part), ils doivent alors faire correspondre:

• Si P1 commence par une carte générique et P2 se termine par une faute générique, utilisez le P1 Wildcard pour manger tous de P2 jusqu'à sa dernière générique, puis utilisez le P2 Wildcard pour manger tous de P1
• Si P1 commence et se termine par une faute générique, utilisez sa carte générique de départ Pour manger P2 jusqu'à sa première génératrice générique, utilisez ensuite le caractère générique P2 pour Manger P1 à sa dernière générique, puis utilisez le dernier Wildcard P1 pour manger le reste de P2

  Sinon, une chaîne (P1) n'a pas de caractères génériques et l'autre chaîne (P2) a des chaînes S1, S2, ... ponctuées de caractères génériques. Donc, juste chercher la première occurrence de S1 en P1, puis pour la première occurrence ultérieure de S2 (à partir de la fin de la correspondance en P1), etc. Si vous trouvez toutes les chaînes, les motifs correspondent, sinon ils ne 't.