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

Question

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

例如，这两个字符串是重叠的简单情况:

1. Hello*World
2. Hel*

但所有这些都是简单情况:

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

是否有已发布的算法来执行此操作？或者在Windows中是否有实用程序函数或库可以调用或复制？

- Tom Ritter

---

可能是如何检测两个正则表达式在它们可以匹配的字符串中重叠？的重复问题。 - ire_and_curses

@ire_and_curses：不完全是这样。这个问题可以归约为您提供的那个问题，但由于这些类型的通配符比正则表达式严格弱，因此有些解决方案适用于通配符，但对正则表达式并不适用。 - sepp2k

Answer 1

由于每个glob都可以写成一个正则表达式，并且可以找到两个正则表达式的交集（除非它们实际上不是正则表达式，但在这种情况下它们将是），因此您可以通过将它们转换为正则表达式并找到那些的交集来找到两个glob的交集。因此，您可以通过查找正则表达式的交集并检查其是否为空来找出两个globs是否相交。

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

让我们称这两个globs为g1和g2。当且仅当以下情况之一为真时，它们相交：

1. g1和g2都为空或仅包含通配符。
2. g1和g2都不为空，并且以下条件之一为真（让c1是g1的第一个字符，t1是包含剩余字符的字符串-对于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

如果通配符很多，这个算法并不特别高效，但是它很容易实现，而且由于你可能计划在文件名中使用它，我怀疑你不会有超过1000个字符的通配符。

- sepp2k

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

- kdawg

Answer 3

您可以在模式长度总和的时间线性内解决此问题：

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

- 如果p1以通配符开头且p2以通配符结尾，请使用p1通配符吞噬所有p2直到其最后一个通配符，然后使用p2通配符吞噬所有p1 - 如果p1以通配符开头和结尾，则使用其起始通配符吞噬p2直到其第一个通配符，然后使用p2通配符吞噬p1直到其最后一个通配符，然后使用最后一个p1通配符吞噬p2的剩余部分

否则，一个字符串（p1）没有通配符，另一个字符串（p2）有带通配符的字符串s1、s2、...以及标点符号。因此，只需在p1中搜索s1的第一次出现，然后在匹配p1的末尾开始查找s2的第一个后续出现，以此类推。如果找到了所有的字符串，则模式匹配，否则不匹配。

- user2949652

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

- Karol Król

Answer 5

这是一个C++实现的算法，建议采用sepp2k的算法，并进行了轻微修改：

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

- Heghine