Lua病理模式是否具有指数运行时间？

概述众所周知,以递归方式(而不是NFA / DFA)实现的正则表达式在某些情况下可能需要指数运行时间. Lua模式是通过递归匹配器实现的(它们允许回溯),但它们的功能不如正则表达式(忘记％b模式). Lua模式是否需要指数运行时间？并且没有回溯(任何出现的％0,％1,％2 …模式)？如果是这样,我会欣赏一些例子. 是的,lua模式可以采用指数时间.试试跑步： string.find('aaaaaaaa 众所周知,以递归方式(而不是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')

如果你保持模式简单,他们仍然可以合理地运行,所以我会尝试在你自己的数据上测试一些真实的例子.

总结

以上是内存溢出为你收集整理的Lua病理模式是否具有指数运行时间？全部内容，希望文章能够帮你解决Lua病理模式是否具有指数运行时间？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。