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

Question

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

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

1. 你好*世界
2. 你好*

但所有这些也是如此:

1. *.csv
2. 报告*.csv
3. reportsdump.csv

是否发布了用于执行此操作的算法？或者可能是 Windows 中的实用程序函数或我可以调用或复制的库？

Answer 1

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

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

让我们称这两个 glob 为 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

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