regular expressions

the picture

a hiker on a trail full of forks, carrying a bag of breadcrumbs. at every fork they drop a crumb and take the most promising path. dead end? walk back to the last crumb and try the other path. the hiker always finds the way out if there is one, but a trail with lots of forks that all look the same can keep them walking for a very long time.

that's java's regex engine. every +, *, ? and | is a fork.

Pattern and Matcher

import java.util.regex.*;
 
static final Pattern DATE = Pattern.compile("(?<year>\\d{4})-(?<month>\\d{2})-(?<day>\\d{2})");
 
void main() {
    Matcher m = DATE.matcher("due 2026-10-09, paid 2026-10-12");
    while (m.find()) {                                       // every match, left to right
        IO.println(m.group("day") + "/" + m.group("month") + " at index " + m.start());
    }
    IO.println(DATE.matcher("2026-10-09").replaceAll("${day}.${month}.${year}"));
    IO.println(DATE.matcher("on 2026-10-09").matches() + " " + DATE.matcher("on 2026-10-09").find());
    IO.println(Pattern.compile("\\d+").matcher("a1b22c333").results().map(MatchResult::group).toList());
}

09/10 at index 4
12/10 at index 21
09.10.2026
false true
[1, 22, 333]

the three ways to ask:

groups are numbered by their opening parenthesis from 1 (group(0) is the whole match). named groups (?<day>...) are easier to read and survive someone adding a group in front. (?:...) groups without capturing.

the cheat sheet

in a java string literal every backslash is doubled: the regex \d+ is written "\\d+". text blocks don't help (they process escapes too).

how backtracking actually works

greedy .+ first eats everything to the end of the input, then gives characters back one at a time until > can match. so <.+> on <a><b> matches the whole thing, not <a>. lazy .+? does the opposite: it takes one char and only takes more when the rest of the pattern fails.

Matcher m = Pattern.compile("<.+>").matcher("<a><b>");
m.find();
IO.println(m.group());

when backtracking explodes

look at (a+)+b on aaaa…!. there's no b, so it must fail. but before it can say no, it has to try every way of splitting the a's between the inner a+ and the outer +: (aaaa), (aaa)(a), (aa)(aa), (a)(aaa)... that's 2^n-1 ways for n a's. in the figure, 10 a's already take over 10,000 steps, and every extra a doubles it. a+b on the same input: 190.

this is the textbook example of catastrophic backtracking, and here's a twist worth knowing: on modern JDKs this exact pattern is fine. java.util.regex (the comment is right there in jdk 25's Pattern.java) remembers the input positions where a greedy, unbounded group loop already failed, and doesn't try them again. but the shortcut switches off in plenty of real patterns: a bounded repeat {1,99}, a lazy loop, a backreference anywhere in the pattern, a loop nested inside another quantified group.

keep quadrupling and 30 a's lands around 8 seconds, for one 31-character string. if the input comes from a user, that's a denial-of-service bug with a name: ReDoS. the fixes, best first:

• write patterns that can't match the same text two ways. (a+)+ means the same as a+. nested quantifiers over the same characters are the smell.
• possessive or atomic where you know backing up can't help: (a++), (?>a+). they match like greedy ones but drop their breadcrumbs.
• bound the input. check the length before matching untrusted text.
• don't use a regex for things that need a parser (nested brackets, HTML, emails beyond "has an @ and a dot").

replacing and splitting

in a replacement string, $1 and ${name} refer to groups, and \ escapes. which means a replacement that happens to contain a $ blows up: "price: 5".replaceAll("\\d", "$9") throws an IndexOutOfBoundsException ("No group 9"). wrap literal replacements in Matcher.quoteReplacement(...), and literal patterns in Pattern.quote(...). since java 9 you can also pass a function that builds each replacement from the match:

Pattern.compile("\\d+").matcher("a1b22c333").replaceAll(r -> "<" + r.group().length() + ">")   // a<1>b<2>c<3>

(and as you saw in the string api, String.split and String.replaceAll take regexes too, so "a.b".split(".") is an empty array.)