lua - 有指数运行时间的 Lua 病理模式吗？

Question

众所周知，以递归方式(而不是 NFA/DFA)实现的正则表达式在某些情况下可能需要指数运行时间。 Lua 模式是通过递归匹配器实现的(它们允许回溯)，但它们不如正则表达式强大(忘记 %b 模式)。

Lua 模式是否需要指数运行时间？并且没有回溯(任何出现的 %0、%1、%2... 模式)？如果是这样，我会欣赏一些例子。

Answer 1

是的，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')

如果你保持模式简单，它们仍然可以相当快地运行，所以我会尝试在你自己的数据上测试一些真实的例子。