如何判断两个通配符是否重叠?

因为每个glob都可以写成正则表达式,并且可以找到两个正则表达式的交集(除非它们不是真正的正则表达式,但在本例中是这样),所以可以通过将它们转换为正则表达式,然后找到整数来找到两个glob的交集。对那些的省略。因此,通过查找正则表达式的交集并检查它是否为空,可以确定两个球是否相交。

但是,由于globs比正则表达式更受限制,因此 许多的 更简单的方法:

让我们把这两个球称为g1和g2。它们相交于敌我识别

1. g1和g2都是空的,或者只包含通配符。
2. g1和g2都不是空的,并且以下条件之一为真(让c1是g1和t1的第一个字符,包含其余字符的字符串-对于g2和c2和t2相同):
   1. C1和C2相等,T1和T2相交
   2. c1和/或c2是通配符,t1与g2相交
   3. c1和/或c2是通配符,g1与t2相交

Haskell中的一个示例实现:

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

如果globs包含很多通配符,这个算法就不是特别有效了,但是它很容易实现,而且由于您可能计划将它与文件名一起使用,所以我怀疑globs的长度会超过1000个字符。

据我所知,您试图确定regex是否与另一个regex正交? 如果是这样的话,这不是一个微不足道的问题。

这里有更多关于 Theory.

以下是解决方案: Java library.

用途:

/**
 * @return true if the two regexes will never both match a given string
 */
public boolean isRegexOrthogonal( String regex1, String regex2 ) {
   Automaton automaton1 = new RegExp(regex1).toAutomaton();
   Automaton automaton2 = new RegExp(regex2).toAutomaton();
   return automaton1.intersection(automaton2).isEmpty();
}

这里是一个由Sepp2k提出的算法的C++实现,稍加修改:

bool intersect(const std::string& pattern1, const std::string& pattern2) {
    if(pattern1.empty() && pattern2.empty()) return true;
    if("*" == pattern1 || "*" == pattern2) return true;

    if(pattern2.empty() && '*' == pattern1[0]) return true;
    if(pattern1.empty() && '*' == pattern2[0]) return true;

    if(pattern1.empty() || pattern2.empty()) return false;

    char c1 = pattern1[0];
    char c2 = pattern2[0];
    string subPattern1 = pattern1.substr(1);
    string subPattern2 = pattern2.substr(1);


    if('*' == c1 && '*' == c2)
        return intersect(pattern1, subPattern2) && intersect(subPattern1, pattern2);

    if('*' == c1 && intersect(pattern1, subPattern2)
       || '*' == c2 && intersect(subPattern1, pattern2)
       || c1 == c2 && intersect(subPattern1, subPattern2)) {
        return true;
    }

    return false;
}

为了它的价值,这是 一 从c(我使用了显式的 return true; 和 return false; 调用,连同注释,以提高算法的可读性):

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;
}