title: Regular expressions with O(N) and backreferences support
body: <p>As you may know there are two different kinds of regular expressions implementations: one uses backtracking (pcre) and the other one uses finite automata (re2).</p>
  
  <p>Both of those algorithms have their limitations: in specific cases pcre can take exponential time to find a match and finite automata does not support backreferences.</p>
  
  <p>Pcre implementation supports backreferences, very inefficient in matching expressions like <code>/a?a?a?a?aaaa/</code> against <code>aaaa</code>, the more <code>a</code>'s expression and input have - the longer it will take and with 30+ of them it will take a lot if time.</p>
  
  <p>Version with finite automata handles all those implementations nicely and have O(N) 
  complexity from input, but does not supports backreferences:</p>
  
  <p>pcre time against complex expressions - <a href="http://i.stack.imgur.com/D4gkC.png" rel="nofollow">http://i.stack.imgur.com/D4gkC.png</a>
  NFA handles those, but does not supports backreferences - <a href="http://i.stack.imgur.com/t2EwI.png" rel="nofollow">http://i.stack.imgur.com/t2EwI.png</a></p>
  
  <p>Some information on backreferences support:</p>
  
  <p>RE2 - <a href="http://code.google.com/p/re2/" rel="nofollow">http://code.google.com/p/re2/</a></p>
  
  <p><em>The  one significant exception is that <strong>RE2 drops support for backreferences</strong>  and generalized zero–width assertions, because they <strong>cannot be  implemented efficiently</strong>.</em></p>
  
  <p>Thompson NFA - <a href="http://swtch.com/~rsc/regexp/regexp1.html" rel="nofollow">http://swtch.com/~rsc/regexp/regexp1.html</a></p>
  
  <p><em>As mentioned earlier, <strong>no one knows how to implement regular  expressions with backreferences efficiently</strong>, though no one can prove  that it's impossible either. (Specifically, the problem is NP–complete,  meaning that if someone did find an efficient implementation, that  would be major news to computer scientists and would win a million  dollar prize.)</em></p>
  
  <p>So I created my own version which both supports backreferences and has O(N) complexity. It written in haskell and about 600 (~200 of them are blank and ~200 - type declarations, which can be skipped) lines long. It chews through <code>/a?a?aa/</code> against <code>aa</code> (with 100 of <code>a</code>) in about 10 seconds and as far as I know it is the only version which can match</p>
  
  <pre><code>/a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?(a?a?a?a?a?a?a?a?a?a?aaaaaaaaaa)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\1/
  </code></pre>
  
  <p>against </p>
  
  <pre><code>aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
  </code></pre>
  
  <p>in sane (about 10 seconds) time. It of course supports all other features listed in basic regex specification which I found somewhere on the Internets.</p>
  
  <p>The question is: is it really a "major news to computer scientists" and what should I do if it is?</p>
  
  <p>PS: I will show sources in about a week - I still want to run some tests with profiler and replace several internal data structures.</p>