R..*_*R.. 18 c regex string substring pattern-matching
编辑: WHOOPS!很大的承认,我搞砸了?in fnmatchpattern语法的定义,似乎已经提出(并且可能已经解决)一个更难的问题,就像它.?在正则表达式中一样.当然,它实际上应该像.正则表达式一样(恰好匹配一个字符,而不是零或一个).这反过来意味着我最初的减少问题的工作足以解决(现在相当无聊)原始问题.解决更难的问题仍然很有趣; 我可能会在某个时候写出来.
从好的方面来说,这意味着像2way/SMOA针分解这样的东西可能适用于这些模式的可能性要大得多,这反过来又可以产生比原本更好的O(n)甚至O(n/m)性能.
在问题标题中,m设为模式/针n的长度,并且是与其匹配的字符串的长度.
这个问题对我很感兴趣,因为我看到/使用过的所有算法都有病态性能不佳和可能的堆栈溢出漏洞,这是由于回溯或需要动态内存分配(例如DFA方法或者只是避免在回调时进行回溯)如果某个程序fnmatch用于授予/拒绝某种访问权限,则会出现故障情况.
我愿意相信正则表达式匹配不存在这样的算法,但文件名模式语言比正则表达式简单得多.我已经将问题简化到可以假设模式不使用该*字符的程度,并且在这个修改过的问题中,您不匹配整个字符串,而是搜索字符串中模式的出现(如子字符串)匹配问题).如果你进一步简化语言并删除?字符,语言只是由固定字符串和括号表达式的连接组成,这很容易在O(mn)时间和O(1)空间中匹配,O(n)如果针分解,也许可以改进2way和SMOA子串搜索中使用的技术可以扩展到这种括号模式.然而,天真的每一个都?要求试验有或没有?消耗一个角色,带来时间因素在2^q哪里q是?模式中的字符数.
有人知道这个问题是否已经解决,或者有解决问题的想法？
注意:在定义O(1)空间时,我使用的是Transdichotomous_model.
注2:本网站详细介绍了我引用的2way和SMOA算法:http://www-igm.univ-mlv.fr/~lecroq/string/index.html
好的，这就是我解决问题的方法。
\n\n尝试将模式的初始部分与*字符串匹配到第一个部分。如果失败，就退出。如果成功，则丢弃模式和字符串的初始部分；我们已经受够了。（如果我们在击中 a 之前击中模式的末尾*，则我们有一个匹配，当且仅当我们也到达了字符串的末尾。）
一直跳到模式的结尾（最后一个之后的所有内容*，如果模式以 a 结尾，则可能是零长度模式*）。计算匹配它所需的字符数，并检查字符串末尾的字符数。如果它们无法匹配，我们就完成了。如果它们匹配，则丢弃模式和字符串的这个组成部分。
现在，我们留下了一个（可能是空的）子模式序列，所有子模式的两侧都有*'s。我们尝试在字符串的剩余部分中按顺序搜索它们，获取每个匹配项的第一个匹配项，并丢弃整个匹配项中字符串的开头。如果我们以这种方式找到每个组件的匹配项，那么我们就得到了整个模式的匹配项。如果任何组件搜索失败，则整个模式将无法匹配。
该算法没有递归，仅在字符串/模式中存储有限数量的偏移量，因此在转二分模型中它是 O(1) 空间。步骤 1 的时间为 O(m)，步骤 2 的时间为 O(n+m)（或者，如果我们假设输入字符串长度已知，但我假设是 C 字符串，则为 O(m)），并且步骤3 是（使用朴素搜索算法）O(nm)。因此，整个算法的时间复杂度为 O(nm)。也许可以将步骤 3 改进为 O(n)，但我还没有尝试过。
\n\n最后，请注意，最初的较难问题可能仍然有助于解决。这是因为我没有考虑多字符整理元素，大多数人实现正则表达式等往往会忽略这些元素，因为它们很难正确处理，并且没有标准 API 与系统区域设置交互并获取必要的信息来获取他们。但话虽如此，这里有一个例子：假设ch是一个多字符整理元素。然后[c[.ch.]]可能会消耗 1 或 2 个字符。我们又回到了需要我在原来的答案中描述的更先进的算法，我认为这需要O(log m)空间，也许比O(nm)时间更多（我O(n\xc2\xb2m)最多猜测）。目前我对实现多字符整理元素支持没有兴趣，但它确实留下了一个很好的开放问题......