regex - 如何高效实现.*a.*b.*这样的正则表达式？

Question

我想匹配像 Colibri 这样的文件名做。我尝试用正则表达式来解决。

在 Colibri 中搜索的工作原理是，您在文件名中键入按顺序排列的字符，它会在文件名中按顺序查找所有具有这些字符的文件。例如，对于“ab”，它会找到“cabal”、“ab”和“achab”。

在字母之间简单插入 .* 是可行的(所以搜索字符串“ab”变成了正则表达式 .*a.*b.*)，但我想它在大量文件上。

到目前为止，我有 O(N*???)，其中 N 是文件名的数量，而 ???充其量是线性复杂度(我假设我的语言使用 NFA)。我不太关心空间复杂性。我应该选择什么样的数据结构或算法来提高效率(时间复杂度)？

Answer 1

如果您只想检查搜索字符串 search 中的字符是否以相同的顺序包含在另一个字符串 str 中，您可以使用这个简单的算法:

pos := -1
for each character in search do
    pos := indexOf(str, character, pos+1)
    if pos is -1 then
        break
    endif
endfor
return pos

此算法返回 str 中 search 最后一个字符的偏移量，否则返回 -1。它的运行时间为 O(n)(您可以用一个简单的 indexOf 循环替换 while，该循环比较 str 中的字符与 pos 到 Length(str)-1 并返回偏移量或 -1。