具有指数运行时间的PCRE正则表达式

Question

在某些情况下，使用递归回溯的正则表达式实现可能会呈现指数运行时间。

我试图找到PCRE引擎的这种病理正则表达式。

我试过了几个正则表达式，它们是Perl正则表达式的指数（例如this one），但它们都没有在我的测试中展现PCRE的指数运行时。

Answer 1

在你的测试中，所有的正则表达式都会失败吗？当他们确实失败时，你是否明确知道为什么？也许匹配失败，因为正则表达式引擎检测到过度的回溯。我不知道如果这事也没发生，但尝试正则表达式应该成功，像这样的：

(?i)lorem(?:.|\s)*pri\. 

使用使用RegexBuddy，我应用了正则表达式下面的文本的第一个段落，它突出了整款如预期。当我在段落结尾删除了这段时间时，高亮显示出来了，调试人员说它已经在一百万次操作后放弃了。那里并不令人意外，但是当我把这段时间放回去并添加第二段时，它仍然失败 - 再次回溯太多。

---

Lorem存有tritani impedit civibus EI PRI，legimus antiopam没有sed的，现状ID everti forensibus maiestatis。 Vim ad intellegat consequuntur。 Te dicam impedit inciderint mea。 Usu prompta alterum contentiones no，ut esse fabellas splendide pri。

Ne utroque nominavi moderatius qui，ius at suas velit nihil，vidit blandit facilisi pri ut。 Adfefefeit reprehendunt，mea ex quem ipsum complectitur。 Veri cetero feugait cu usu，in dolor corpora adolescens vim，at sit voluptua placerat sadipscing。 Minim admodum constituam eos ut，vix ut movet causae tractatos，in pro dicat dicta dolores。 Impetus praesent eum no。