3 ms·
Regex matching in P with backreference (2019)
- thealig 3y agoFYI the title stated in the github readme itself is misleading and incomplete.. in the fine print clarifies that this is in polynomial time "in the size of the input text for a fixed number of backreferences in the pattern."
- tgv 3y agoIs that somehow special? CFG parsing is O(n^3) worst case using Earley's algorithm, regexp is faster. Back-references is a matter of inserting extra non-terminals. I once wrote a regexp to DFA with backreferences. I never checked the correctness, though.
- davidgay 3y agoThe perl version of regexps is np-hard... https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
- teraflop 3y agoIt is easy to write a regexp with backreferences that cannot be represented by any DFA. So I'd say the correctness of your implementation is doubtful. For example, the language defined by the regexp /([ab]*)\1/ is neither regular nor context-free.
- tgv 3y agoMy bad. I had missed the fact that it was in the pattern.