To Vladimir Prus:
Interesting. Is the algorithm from some published paper that you could link/post? Or do you have a formal description?
The paper describing this algorithm is submitted for publication (offline) but not out yet. I am considering possibilities of publishing another version online---can you advise me on the subject of the best way to do it (other than creating & promoting my own site :) )? To Reid Sweatman:
Very nice. I've banged up against that one painfully recently (not with Boost's regex engine, be it noted <g>), and frankly, that's quite a guarantee given the features you mention.
Well, I developed this one without boost.regex in mind, firstly. It's just that I don't feel like creating a whole new regex library from scratch, and regex seems to be a right place to fit this in. To Eric Niebler:
Interesting. You say it supports substring capturing. Does it also support backreferences?
Unfortunately, no. It's proven somewhere out there that regex matching with backrefs is NP-hard---so, I guess, no linear guarantee ever. <sob> -- Best regards, Vladimir Pozdyayev.