From: Vladimir Pozdyayev (ardatur_at_[hidden])
Date: 2004-10-26 01:13:50
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.
-- Best regards, Vladimir Pozdyayev.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk