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

Question

给定两个带有 * 通配符的字符串，我想知道是否可以创建一个与这两个字符串匹配的字符串。

例如，这两个是重叠的简单情况：

1. Hello*World
2. Hel*

但所有这些都是：

1. *.csv
2. reports*.csv
3. reportsdump.csv

是否有为此发布的算法？或者也许是 Windows 中的实用函数或我可以调用或复制的库？

Answer 1

由于每个 glob 都可以写成正则表达式，并且可以找到两个正则表达式的交集（除非它们不是真正的正则表达式，但在这种情况下它们是正则的），因此您可以通过将它们转换为来找到两个 glob 的交集正则表达式，然后找到它们的交集。因此，您可以通过查找正则表达式的交集并检查它是否为空来确定两个 glob 是否相交。

然而，由于 glob 比正则表达式受到更多限制，因此有一种更简单的方法：

让我们将这两个 glob 称为 g1 和 g2。它们相交当且

1. 仅当 g1 和 g2 均为空或仅包含通配符。
2. g1 和 g2 都不为空，并且以下条件之一为真（令 c1 为 g1 的第一个字符，t1 为包含其余字符的字符串 - 对于带有 c2 和 t2 的 g2 来说相同）：
   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

该算法不是如果 glob 包含大量通配符，则效率不会特别高，但它很容易实现，并且由于您可能计划将其与文件名一起使用，因此我怀疑您的 glob 长度将超过 1000 个字符。

Answer 2

无论如何，这里是来自 sepp2k 在 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;
}

Answer 3

您可以在模式长度总和的时间上线性地解决这个问题：

如果两个字符串都以非通配符开头或结尾，请检查它们是否匹配，直到一个模式遇到通配符（否则它们不匹配）。这将问题减少到至少一种模式以通配符开始且至少一种模式以通配符结束的情况。如果两个模式都有通配符（某处），那么它们必须匹配：

• 如果 p1 以通配符开头并且 p2 以通配符结尾，则使用 p1
  通配符吃掉所有 p2 直到最后一个通配符，然后使用 p2
  通配符会吃掉所有 p1
• 如果 p1 以通配符开头和结尾，则使用其起始通配符
  吃掉 p2 直至其第一个通配符，然后使用 p2 通配符
  把p1吃到最后一个通配符，然后用最后一个p1通配符吃
  否则

，一个字符串 (p1) 没有通配符，而另一个字符串 (p2) 则包含用通配符标点的字符串 s1,s2,...。因此，只需搜索 s1 在 p1 中的第一次出现，然后搜索 s2 的第一次后续出现（从 p1 中的匹配末尾开始），依此类推。如果找到所有字符串，则模式匹配，否则它们不匹配't。

Answer 4

据我了解，您尝试确定一个正则表达式是否与另一个正则表达式正交？
如果是这样，这就是一个非常不简单的问题。

以下是有关理论的更多信息。

这是解决方案：Java 库。

用法：

/**
 * @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();
}

Answer 5

下面是 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;
}