如何有效地实现正则表达式,如.*a.*b.*？

Question

我想匹配像Colibri那样的文件名.我试图通过正则表达式来解决它.

在Colibri中搜索的工作原理是,您可以在文件名中按顺序键入字符,并在文件名中按顺序查找具有这些字符的所有文件.例如,对于"ab",它找到"cabal","ab"和"achab".

简单插入.*字母之间的工作(所以搜索字符串"ab"成为正则表达式.*a.*b.*),但我想在大量文件上进行.

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

Answer 1

如果您只想检查搜索字符串搜索的字符是否以相同的顺序包含在另一个字符串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和否则为-1.它的运行时在O(n)中(你可以用indexOf一个简单的while循环代替它,它将str中的字符从pos与str(str)-1进行比较,并返回偏移量或-1).