Lua是否存在具有指数运行时间的病态模式？

2015-1-29 14:53:53
收藏：0
阅读：62
评论：1

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

Lua模式需要指数运行时间吗？没有回溯（任何%0，%1，%2...模式的出现）？如果有的话，我将感激一些例子。

点赞
用户298029
用户298029

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

如果模式保持简单，则它们仍然可以以合理的速度运行，因此建议尝试使用自己的数据进行一些真实的例子测试。

2015-01-29 18:17:26

作者:

用户3368561

用户3368561
推荐文章