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

发布时间：2020-12-14 05:38:28 所属栏目：百科来源：网络整理

导读：我想匹配像 Colibri这样的文件名.我试图通过正则表达式来解决它. 在Colibri中搜索的工作原理是,您可以在文件名中键入按顺序排列的字符,并在文件名中按顺序查找所有具有这些字符的文件.例如,对于“ab”,它找到“cabal”,“ab”和“achab”. 简单插入.*之间的

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

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

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!