<!-- mobian-agent-page publisher="dailydev" canonical="https://daily.dev/posts/yes-all-longest-regex-matches-in-linear-time-is-possible-3i3fe1s8z" -->

---
title: yes, all longest regex matches in linear time is possible
description: Most regex engines advertised as 'linear time' — including RE2, Go's regexp, and Rust's regex crate — only guarantee linear time for a single match. Finding...
canonical: https://daily.dev/posts/yes-all-longest-regex-matches-in-linear-time-is-possible-3i3fe1s8z
twitter:card: summary_large_image
twitter:site: @dailydotdev
og:type: website
og:site_name: daily.dev
og:title: yes, all longest regex matches in linear time is possible | daily.dev
og:description: Most regex engines advertised as 'linear time' — including RE2, Go's regexp, and Rust's regex crate — only guarantee linear time for a single match. Finding...
og:url: https://daily.dev/posts/yes-all-longest-regex-matches-in-linear-time-is-possible-3i3fe1s8z
og:image: https://api.daily.dev/og/posts/3i3FE1s8z.png
og:image:alt: yes, all longest regex matches in linear time is possible
og:image:width: 1200
og:image:height: 630
og:locale: en
---

> ## Documentation Index
> Fetch the complete documentation index at: https://daily.dev/llms.txt
> Use this file to discover all available pages before exploring further.

# yes, all longest regex matches in linear time is possible

**[Lobsters](https://daily.dev/sources/lobsters)** · 11 min read · 1 upvotes · 0 comments

## Summary

Most regex engines advertised as 'linear time' — including RE2, Go's regexp, and Rust's regex crate — only guarantee linear time for a single match. Finding all matches degrades to O(n²) due to the 'loop around a DFA' approach. The author presents RE#, a regex engine that solves this with a two-pass bidirectional algorithm that finds all leftmost-longest (POSIX) matches in true linear time without changing semantics. A 'hardened' mode using an O(n*S) forward scan is also available for adversarial inputs, trading 3-9x constant-factor slowdown for guaranteed linear behavior. Benchmarks show RE# is competitive with Rust's regex crate on literal-heavy patterns using AVX2/NEON intrinsics. Current limitations include no capture groups and no lazy quantifiers. The post also distinguishes RE# from REmatch (VLDB 2023), which solves the different problem of enumerating all overlapping matches.

## Full article

daily.dev links to this article rather than hosting it. Read it at the original source: <https://iev.ee/blog/all-longest-regex-matches-in-linear-time/>

## Similar posts on daily.dev

- [finding all regex matches has always been O\(n²\). even in the engines built to prevent it](https://daily.dev/posts/finding-all-regex-matches-has-always-been-o-n-even-in-the-engines-built-to-prevent-it-6av6qyuxr) · Hacker News · 4 upvotes · 0 comments
- [RE\#: how we built the world's fastest regex engine in F\#](https://daily.dev/posts/re-how-we-built-the-world-s-fastest-regex-engine-in-f--s1rdfweqf) · Hacker News · 4 upvotes · 0 comments
- [Labeled matches: why is this not in every regex engine?](https://daily.dev/posts/labeled-matches-why-is-this-not-in-every-regex-engine--lpfqh8kio) · Lobsters · 0 upvotes · 0 comments
- [The regex that froze a shipped app for two minutes](https://daily.dev/posts/the-regex-that-froze-a-shipped-app-for-two-minutes-wtsmla40m) · Medium · 0 upvotes · 0 comments
- [A Ruby Regular Expression Engine](https://daily.dev/posts/a-ruby-regular-expression-engine-titxotkfv) · RUBYLAND · 0 upvotes · 0 comments

---

Tags: [#rust](https://daily.dev/tags/rust)

[View this post on daily.dev](https://daily.dev/posts/yes-all-longest-regex-matches-in-linear-time-is-possible-3i3fe1s8z)

```json
{"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]}
{"@context":"https://schema.org","@type":"TechArticle","headline":"yes, all longest regex matches in linear time is possible","url":"https://daily.dev/posts/yes-all-longest-regex-matches-in-linear-time-is-possible-3i3fe1s8z","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/yes-all-longest-regex-matches-in-linear-time-is-possible-3i3fe1s8z"},"datePublished":"2026-03-18T11:14:49.744Z","dateModified":"2026-03-18T11:15:17.285Z","description":"Most regex engines advertised as 'linear time' — including RE2, Go's regexp, and Rust's regex crate — only guarantee linear time for a single match. Finding...","image":"https://media.daily.dev/image/upload/s--VDukGCjf--/f_auto/v1722860399/public/Placeholder%2002","thumbnailUrl":"https://media.daily.dev/image/upload/s--VDukGCjf--/f_auto/v1722860399/public/Placeholder%2002","isAccessibleForFree":true,"articleSection":"Lobsters","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Lobsters","logo":"https://media.daily.dev/image/upload/s--tl8v_Fku--/f_auto,t_logo/v1698841318/logos/lobste.jpg","url":"https://daily.dev/sources/lobsters"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/yes-all-longest-regex-matches-in-linear-time-is-possible-3i3fe1s8z","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":1},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"rust","timeRequired":"PT11M"}
{"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Lobsters","item":"https://daily.dev/sources/lobsters"},{"@type":"ListItem","position":3,"name":"yes, all longest regex matches in linear time is possible"}]}
```

