编辑:糟糕!大承认，我在 fnmatch 模式语法中搞砸了 ? 的定义并且似乎已经提出(并且可能解决)了一个更难的问题，它的行为类似于 .? 在正则表达式中。当然，它实际上应该表现得像正则表达式中的 .(匹配恰好一个 字符，而不是零或一个)。这反过来意味着我最初的问题减少工作足以解决(现在相当无聊的)原始问题。不过，解决更难的问题仍然很有趣；我可能会在某个时候写出来。
从好的方面来说，这意味着像 2way/SMOA 针分解这样的东西更有可能适用于这些模式，这反过来可能会产生比最初期望的更好的 O(n) 甚至 O(n/m) 性能。
在问题标题中，设 m 为图案/针的长度，n 为与之匹配的字符串的长度。
我对这个问题很感兴趣，因为我见过/使用过的所有算法要么在病态上表现不佳，要么由于回溯而可能出现堆栈溢出漏洞，或者需要动态内存分配(例如，对于 DFA 方法或只是避免进行回溯在调用堆栈上)，因此如果程序使用 fnmatch 授予/拒绝某种访问权限，则失败案例也可能很危险。
我愿意相信正则表达式匹配不存在这样的算法，但文件名模式语言比正则表达式简单得多。我已经将问题简化到可以假定模式不使用 * 字符的程度，并且在这个修改后的问题中，您不是在匹配整个字符串，而是在搜索出现的字符串中的模式(如子串匹配问题)。如果进一步简化语言并删除 ? 字符，则该语言只是由固定字符串和括号表达式的串联组成，这可以在 O(mn) 中轻松匹配> 时间和 O(1) 空间，如果 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(来自 Google)的 re2 正则表达式引擎？
它是一个基于确定性有限自动机的正则表达式匹配引擎，不同于通常的实现(Perl、PCRE)使用回溯来模拟非确定性有限自动机。具体设计目标之一是消除您提到的灾难性回溯行为。
它不允许某些 Perl 扩展，例如搜索模式中的反向引用，但您不需要它来进行 glob 匹配。
我不确定它是否特别保证 O(mn) 时间和 O(1) 内存限制，但它足以运行 Google 代码搜索存在时的服务。
至少，看看内部并了解其工作原理应该很酷。 Russ Cox 撰写了三篇关于 re2 的文章 - one , two , three - 和 re2 code是开源的。
关于c - 是否有用于 POSIX 文件名匹配 (fnmatch) 的已知 O(nm)-time/O(1)-space 算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10343351/