Why does Negative Lookahead times out with And/Or Pipe
<p>I have an And/Or regex i.e (PatternA|PatternB) in which I only take PatternA if PatternB does not exist (PatternB always comes after PatternA but is more important) so I put a negative lookahead in the PatternA Pipe.</p>

<p>This works on shorter text blocks:</p>

<p><a href="https://regex101.com/r/bU6cU6/5" rel="nofollow">https://regex101.com/r/bU6cU6/5</a></p>

<p>But times out on longer text blocks:</p>

<p><a href="https://regex101.com/r/bU6cU6/2" rel="nofollow">https://regex101.com/r/bU6cU6/2</a></p>

<p>What I don't understand is if I put PatternA with the Neg Look ahead alone in the same long text block it takes only 32 steps to reject it:</p>

<p><a href="https://regex101.com/r/bU6cU6/3" rel="nofollow">https://regex101.com/r/bU6cU6/3</a></p>

<p>and if I put PatternB alone in the same long text block it only takes 18 steps to accept it:</p>

<p><a href="https://regex101.com/r/bU6cU6/4" rel="nofollow">https://regex101.com/r/bU6cU6/4</a></p>

<p>So I am not sure why it is taking 100,000+/timeout to first reject (32 steps) then accept (18 steps) with the pipes. Is there another/better way to construct so it checks PatternA first than PatternB because now it is doing something I don't understand to go from 50 steps to 100k +.</p>

<p>Your main problem is the position of the lookahead.  The lookahead has to be tried at every position, and it has to scan all the remaining characters every time.  The longer test string is over 3500 characters long; that adds up.</p>

<p>If your regex isn't anchored, you should always try to start it with something concrete that will fail or succeed quickly--literal text is the best.  In this case, it's obvious that you can move the lookahead back: <code>Option1:\*(?!.*Option2)</code> instead of <code>(?!.*Option2)Option1:\*</code>.  (Notice the lack of trailing <code>.*</code> in the lookahead; you didn't need that.)</p>

<p>But why is PatternA so much quicker when you match it alone?  Internal optimizations.  When the regex is just <code>(?!.*Option2.*)Option1:\*.*?(?P&lt;Capture&gt;(Bob|David|Ted|Alice))</code>, the regex engine can tell that the match must start with <code>Option1:*</code>, so it goes straight to that position for its first match attempt.  The longer regex is too complicated, and the optimization doesn't occur.</p>

<p>You can test that by using the "regex debugger" option at Regex101, then checking <code>DISABLE INTERNAL ENGINE OPTIMIZATIONS</code>.  The step count goes back to over 100,000.</p>

python regex timeout negative-lookahead