具有指數運行時間的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。