编辑：哎呀！大承认，我搞砸了fnmatch模式语法中?的定义，并且似乎提出了（并可能解决）了一个更难的问题，它的行为类似于正则表达式中的.?。当然，它实际上应该表现得像正则表达式中的.（只匹配一个字符，而不是零或一）。这反过来意味着我最初的问题减少工作足以解决（现在相当无聊的）原始问题。不过，解决更难的问题仍然很有趣;我可能会在某个时候写下来。
从好的方面来说，这意味着像 2way/SMOA 针分解这样的东西更有可能适用于这些模式，这反过来又会产生比最初期望的更好的O(n)甚至O(n/m)性能。
在问题标题中，m是图案/针的长度，n是与其匹配的字符串的长度。
这个问题对我感兴趣，因为我见过/使用的所有算法要么性能异常差，要么由于回溯而可能出现堆栈溢出漏洞，要么需要动态内存分配（例如，对于 DFA 方法或只是避免在调用堆栈上进行回溯），因此有失败的情况，如果程序使用 fnmatch 授予/拒绝某种访问权限，也可能很危险。
我愿意相信正则表达式匹配不存在这样的算法，但文件名模式语言比正则表达式简单得多。我已经将问题简化到可以假设模式不使用*字符的程度，在这个修改后的问题中，您不是匹配整个字符串，而是搜索字符串中模式的出现（如子字符串匹配问题）。如果进一步简化语言并删除?字符，则语言仅由固定字符串和括号表达式的串联组成，这可以很容易地在时间和 O（1） 空间O(mn)匹配，如果 2way 和 SMOA 子字符串搜索中使用的指针分解技术可以扩展到这样的括号模式，这也许可以改进到O(n)。然而，天真地，每个?都需要在有或没有消耗字符?的情况下进行试验，从而带来2^q的时间因素，其中q是模式中?字符的数量。
谁知道这个问题是否已经解决，或者有解决它的想法？
注意：在定义 O（1） 空间时，我使用的是Transdichotomous_model。
注2：本网站详细介绍了我引用的2way和SMOA算法：http://www-igm.univ-mlv.fr/~lecroq/string/index.html
你有没有研究过Russ Cox（谷歌的）re2正则表达式引擎？
正则表达式匹配引擎，它不同于通常的实现（Perl，PCRE），使用回溯来模拟非确定性有限自动机。其中一个具体的设计目标是消除你提到的灾难性回溯行为。
它不允许一些 Perl 扩展，例如搜索模式中的反向引用，但您不需要它来进行 glob 匹配。
我不确定它是否保证了O(mn)时间和O(1)内存限制，但它足以在 Google 代码搜索服务存在时运行它。
至少看看里面看看它是如何工作的应该是很酷的。Russ Cox写了三篇关于re2的文章 - 一，二，三 - re2代码是开源的。
编辑：哎呀！大承认，我在模式语法中搞砸了?的定义fnmatch并且似乎已经解决了一个更难的问题，它的行为类似于正则表达式中的.?。当然，它实际上应该表现得像正则表达式中的.（只匹配一个字符，而不是零或一）。这反过来意味着我最初的问题减少工作足以解决（现在相当无聊的）原始问题。不过，解决更难的问题仍然很有趣;我可能会在某个时候写下来。
更难问题的可能解决方案如下。
我已经在O(log q)空间（其中q是模式中的问号数量，因此q <m）和不确定但似乎优于指数时间的领域找到了似乎是解决方案。>
首先，快速解释一下问题减少。首先打破每个*的模式;它分解为（可能为零长度）初始和最终组件，以及两侧由*两侧的许多内部组件分解。这意味着一旦我们确定初始/最终组件是否匹配，我们就可以对内部匹配应用以下算法：从最后一个组件开始，在从最新偏移量开始的字符串中搜索匹配项。这使得最可能的"大海捞针"字符可以自由匹配早期组件;如果它们不是全部需要的，那也没问题，因为*干预的事实允许我们以后根据需要丢弃尽可能多的，因此尝试"使用更多?标记"的最后一个组件或找到更早出现的组件是没有好处的。然后可以对每个组件重复此过程。请注意，在这里我强烈利用了这样一个事实，即fnmatch表达式中唯一的"重复运算符"是匹配任何字符零次或多次出现的*。同样的缩减不适用于正则表达式。
有了这个，我开始寻找如何有效地匹配单个组件。我允许的时间因子为 n ，所以这意味着可以在字符串中的每个可能位置开始尝试，如果我们失败了，就放弃并移动到下一个位置。这是我们将采取的一般程序（还没有类似Boyer-Moore的技巧;也许它们可以在以后引入）。
对于给定的组件（不包含*，只包含文字字符，与给定集合中的一个字符完全匹配的括号，以及?），它具有可以匹配的最小和最大长度字符串。如果省略所有?字符并将括号表达式计为一个字符，则最小值为长度;如果包含?字符，则最大值为长度。在每个位置，我们将尝试形态组件可以匹配的每个可能长度。这意味着我们执行q+1试验。对于下面的解释，假设长度保持固定（它是最外层的循环，在即将引入的递归之外）。这也固定了字符串的长度（以字符为单位），我们将在这一点上与模式进行比较。
现在这是有趣的部分。我不想遍历所有可能的组合，哪些?字符被使用/不使用。迭代器太大，无法存储。所以我作弊。我将模式组件分成两半，L和R，每个"半"包含一半的?字符。然后，我简单地迭代L中使用了多少个?字符的所有可能性（从 0 到基于上面固定的长度将使用的总字符数），然后确定R中使用的?个字符的数量。这也将我们尝试匹配的字符串划分为将与模式L和模式R匹配的部分。
现在，我们已经减少了检查具有q ?个字符的模式组件是否与特定的固定长度字符串匹配的问题，减少了检查具有q/2 ?个字符的模式组件是否与特定的较小固定长度字符串匹配的两个实例。应用递归。由于每个步骤都涉及?字符的数量减半，因此递归级别的数量受log q的限制。
您可以创建两个字符串的哈希，然后比较它们。哈希计算将以 O（m） 完成，而搜索将以 O（m + n） 为单位完成
您可以使用这样的东西来计算字符串的哈希值，其中 s[i] 是一个字符
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
正如您所说，这是用于文件名匹配，您不能在字符串中有通配符的地方使用它。祝你好运！
我的感觉是这是不可能的。
虽然我不能提供一个防弹的论点，但我的直觉是，你总是能够构造包含 q=Theta（m） ?字符的模式，在某种意义上，算法必须考虑所有 2^q 的可能性。这将需要 O（q）=O（m） 空间来跟踪您当前正在寻找的可能性。例如，NFA 算法使用此空间来跟踪它当前所处的状态集;蛮力回溯方法使用空间作为堆栈（为了增加伤害，除了空间的 O（q） 之外，它还使用 O（2^q） 时间）。
好的，这就是我解决问题的方法。
-
尝试将模式的初始部分与字符串的第一个
*匹配。如果失败，请纾困。如果成功，则丢弃模式和字符串的初始部分;我们已经完成了它们。（如果我们在击中*之前击中模式的末尾，我们有一个匹配，如果我们也到达了字符串的末尾。 -
一直跳到模式的结束端（最后一个
*之后的所有内容，如果模式以*结尾，这可能是零长度模式）。计算匹配它所需的字符数，并从字符串末尾检查这么多字符。如果它们不匹配，我们就完成了。如果它们匹配，则丢弃模式和字符串的此组件。 -
现在，我们留下了一个（可能是空的）子形态序列，所有这些子形态的两侧都是
*的。我们尝试在字符串的剩余部分按顺序搜索它们，为每个匹配项获取第一个匹配项，并在匹配过程中丢弃字符串的开头。如果我们以这种方式找到每个组件的匹配项，我们就得到了整个模式的匹配项。如果任何组件搜索失败，则整个模式无法匹配。
这个 alogorithm 没有递归，只在字符串/模式中存储有限数量的偏移量，所以在跨二分模型中它是 O（1） 空间。第 1 步是时间上的 O（m），第 2 步是时间上的 O（n+m）（如果我们假设输入字符串长度已经知道，但我假设是 C 字符串，则为 O（m），第 3 步是（使用朴素搜索算法）O（nm）。因此，算法在时间上总体上是O（nm）。有可能将步骤 3 改进为 O（n），但我还没有尝试过。
最后，请注意，原来的难题可能仍然有用。那是因为我没有考虑多字符整理元素，大多数实现正则表达式等的人往往会忽略这些元素，因为它们很难正确，并且没有标准的 API 与系统语言环境交互并获取获取它们的必要信息。但话虽如此，这里有一个例子：假设ch是一个多字符整理元素。然后[c[.ch.]]可以使用 1 或 2 个字符。我们又回到了我需要我在原始答案中描述的更高级的算法，我认为它需要O(log m)空间，也许需要O(nm)多一点的时间（我猜充其量是O(n²m)）。目前我对实现多字符整理元素支持没有兴趣，但它确实留下了一个很好的开放问题......