Lua病理模式是否具有指数运行时间?
发布时间:2020-12-14 21:43:31 所属栏目:大数据 来源:网络整理
导读:众所周知,以递归方式(而不是NFA / DFA)实现的正则表达式在某些情况下可能需要指数运行时间. Lua模式是通过递归匹配器实现的(它们允许回溯),但它们的功能不如正则表达式(忘记%b模式). Lua模式是否需要指数运行时间?并且没有回溯(任何出现的%0,%1,%2 …模
众所周知,以递归方式(而不是NFA / DFA)实现的正则表达式在某些情况下可能需要指数运行时间. Lua模式是通过递归匹配器实现的(它们允许回溯),但它们的功能不如正则表达式(忘记%b模式).
Lua模式是否需要指数运行时间?并且没有回溯(任何出现的%0,%1,%2 …模式)?如果是这样,我会欣赏一些例子. 解决方法
是的,lua模式可以采用指数时间.试试跑步:
string.find('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa','a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?' .. 'a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa') 如果你保持模式简单,他们仍然可以合理地运行,所以我会尝试在你自己的数据上测试一些真实的例子. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |