如何不讓正則表達式做出太多步驟？

我有一個簡單的正則表達式（在C＃中使用）：如何不讓正則表達式做出太多步驟？

\becua(?:[a-zA-ZáéíóúñÑÑäëïöü])*\b(.(?!embajada))*\s+embajada

1）字開頭「ecua」
2）無論之後附帶該
3）單詞「Embajada酒店」之後「無論「

但它使太多的步驟，我該如何防止這種情況？我只是希望它能夠通過字符，直到找到「embajada」這個單詞，而不是在每一個字符上都回溯。這似乎是簡單的正則表達式，但是當我用一個更大的文本，它拋出一個災難性的回溯（或超時）當模式失敗

例子：https://regex101.com/r/tQ7mM9/4

在此先感謝

來源

2016-04-13 Crabax

你必須使用'（？= Embajada酒店）'代替'（？！Embajada酒店） '，我想 – rock321987

你的文字中沒有「embajada」這個詞，只有「gembajada」。 –

我會展開它：https://regex101.com/r/iR5eW3/1 –

你可以寫你的模式在一個貪婪的方式，但這次封閉所有量詞在原子組中的部分。要做到這一點，你顯然需要進行試驗以前瞻，但限制太多測試的影響，則可以使用字符類（[^e]這裏）幫助正則表達式引擎僅在有趣的位置進行測試：

\becua(?>\w*[^e]*(?:\Be[^e]*|e(?!mbajada\b)[^e]*)*)embajada

細節：

\becua 
(?> 
    \w*  # last part of "ecua..." 

    [^e]* # all that is not an "e" 
    (?: 
     \Be   # an "e" not at the start of a word 
     [^e]* 
     | 
     e(?!mbajada\b) # an "e" that is not the start of "embajada" 
     [^e]* 
    )*  # repeat as possible 
) # close the atomic group (backtracking is no more possible) 
embajada

When the pattern fails
When the pattern succeeds

現在非貪婪的方法（同樣的想法，以限制非貪婪量詞的影響）：

\becua(?>e*[^e]+)*?\bembajada\b

When the pattern fails
When the pattern succeeds

來源

2016-04-13 19:26:21

一句話：'\ w'會匹配'_'和數字，我認爲'\ p {L}'是一個更好的替代品爲'[a-zA-ZáéíóññÑÑääïöö]'。 –

謝謝兄弟！有用！！我選擇第二個正則表達式是因爲更容易實現（我需要將用戶插入的關鍵字轉換爲正則表達式）。 – Crabax

這是你在找什麼對於？ \b(ecua\w+) .*? (embajada)

來源

2016-04-13 18:29:16 shlatchz

最差的答案得到了所有upvotes。 –

這樣的工作，但在失敗的情況下，使117k步驟，用戶評論一個正則表達式，在同一個案中使66k步驟 – Crabax

試驗上regex101

執行下面是不同方法的比較表。第一個是我的，第二個是修改的OP'sregex，第三個是另一個用戶在這裏給出的答案的修改版本，第四個是Wiktor。不成功的比賽是爲embajada錯誤embajad

+------+--------+--------+--------+--------+-------+------+--------------+ 
|    Regex      | Successful | Unsuccessful | 
+------+--------+--------+--------+--------+-------+------+--------------+ 
| \becua.*embajada       | 310 steps | 167543 steps | 

| \becua(?:.*)\b(.(?=embajada))*embajada | 993 steps | 579122 steps | 

| \becua.*?embajada      | 23897 steps | 167543 steps | 

| (?>\becua\p{L}*\b\s*\S*) 
| (?>(?:\s+(?!embajada)\S*)*)\s+embajada | 18001 steps | 111394 steps | 
+------+--------+--------+--------+--------+-------+------+--------------+

1日的正則表達式似乎需要在成功和不成功的比賽最少的步數

來源

2016-04-13 18:41:17 rock321987

您正在嘗試我的模式從評論:)？尼斯。更好地顯示來自http://regexhero.net/tester的測試。我的最新的'（？> \ becua \ p {L} * \ b \ s * \ S *）（？>（？：\ s +（?! embajada）\ S *）*）\ s + embajada'顯示78，每秒2次迭代。 –

@WiktorStribiżew即將更新 – rock321987

請參閱Casimir的回答，研究該模式。比我的快三倍。 –

如何不讓正則表達式做出太多步驟？

回答

相關問題