<p>Using ICU 4.0 regex library, I find that the following regex is exhibiting exponential time:</p>

<pre><code>actual: "[^&lt;]*&lt;\?"
C code: "[^&lt;]*&lt;\\?"
</code></pre>

<p>Aim: find "&lt;?" where there is no other "&lt;" before it</p>

<p>When running this regex on plain text with no "&lt;" characters at all it appears to take exponential time. If the text has at least a single "&lt;" then it is quick. I don't understand why. </p>

<p>Shouldn't the required match on "&lt;?" prevent this from needing to backtrack? I would have thought that it would try to find the first "&lt;" and then test the rest of the expression. If it can't find a "&lt;" then it would give up because the pattern obviously can't match.</p>

<p>Is this a bug in the ICU regex or is it expected?</p>

The regex engine isn't that smart. It will try to match from
every
position, and
each
time seach for
```
<?
```
from the end, and backtrack until the start of the match-attempt. This gives a quadratic time complexity, O(
n
2
).