Hacker GitHub

← All repos

travisdowns/polyregex

View on GitHub ↗ ★ 9 Java

Regex matching in P with backreference (see fine print)

4 mentions on Hacker News by 3 people: 1 story, 3 comments · first 2019-06-29 · latest 2026-03-24

Mentions per year 4 mentions · busiest year 2019 (1)
20082026
AllStoriesComments NewestTopOldest
  1. …question in my view. [1] https://branchfree.org/2019/04/04/question-is-matching-fixed... [2] https://github.com/travisdowns/polyregex [3] https://news.ycombinator.com/item?id=40431198
    comment by mananaysiempre · 2026-03-24 · in Finding all regex matches has always been O(n²)
  2. …can match arbitrary context-free languages in “merely” cubic time. But it’s not exponential. [1] https://github.com/travisdowns/polyregex
    comment by mananaysiempre · 2024-05-23 · in Regular expression matching can be simple and fast (2007)
  3. ▲ 11
    Regex matching in P with backreference (2019)
    story by userbinator · 2023-07-21 · 5 comments
  4. Here's a regex implementation that is polynomial in time and space: https://github.com/travisdowns/polyregex If you want to use extender regex that includes backreferences, it is still polynomial as long as the number of backreferences is…
    comment by BeeOnRope · 2019-06-29 · in Regular Expression Matching Can Be Simple and Fast (2007)