Regex

A regular expression describes a text pattern. A backtracking engine tries it at each position, matching token by token — and when a greedy quantifier took too much, it gives characters back and tries again.

/\w+@\w+\.com/

\w+@\w+\.com
m0a1i2l3␣4a5s6h7a8@9a10i11c12a13n14c15o16d17e18.19c20o21m22
  • Matched so far
  • Testing
  • Backtracking
  • Final match

Try to match the pattern somewhere in the text, starting at each position from the left. 7 tokens: \w+ @ \w+ \. c o m.

Step 1 / 74
Character tests
0
Backtracks
0

Supports . \d \w \s [a-z] [^…] * + ? {n} {n,m} ^ $ — not groups or |.

Step by step

The example above, written out — the same steps the animation plays.

  1. 1/\w+@\w+\.com/. Try to match the pattern somewhere in the text, starting at each position from the left. 7 tokens: \w+ @ \w+ \. c o m.
  2. 2Try from position 0. Start at the first character.
  3. 3\w+ vs "m". "m" is a letter, digit or _.
  4. 4\w+ vs "a". "a" is a letter, digit or _.
  5. 5\w+ vs "i". "i" is a letter, digit or _.
  6. 6\w+ vs "l". "l" is a letter, digit or _.
  7. 7\w+ vs " ". " " is not a letter, digit or _.
  8. 8@ vs " ". " " is not "@".
  9. 9@ needs 1. Not enough matching characters here.
  10. 10Backtrack: \w+ gives one back. \w+ took 4; try with 3 so the rest of the pattern gets a chance.
  11. 11@ vs "l". "l" is not "@".
  12. 12@ needs 1. Not enough matching characters here.
  13. 13Backtrack: \w+ gives one back. \w+ took 3; try with 2 so the rest of the pattern gets a chance.
  14. 14@ vs "i". "i" is not "@".

…and 60 more steps — press Play above to watch them all.

What's happening?

  1. The engine starts at position 0 and tries to match every token in order; if it fails, it slides one position right and starts over.
  2. Quantifiers like * and + are greedy: they take as many characters as they can first.
  3. If the rest of the pattern then fails, the quantifier gives back one character at a time (backtracking) until everything fits — or no option is left.

Complexity

Time
Usually linear-ish · exponential in the worst case for a backtracking engine
Space
O(pattern length) for the backtracking stack

Where you'll meet it

Validating input, search and replace in editors, log parsing, routing rules and data extraction.

Common mistake

Nested or overlapping quantifiers such as (a+)+ or a*a*b on long inputs: the number of ways to split the text explodes. This "catastrophic backtracking" has taken real sites down.

FAQ

What does greedy mean?

A quantifier first takes as much as it can, then gives back only if the rest of the pattern needs it. Add ? (as in .*?) to make it lazy instead.

Why did a* a* … b take so many steps?

With no b in the text, the engine tries every way to share the a's between the quantifiers before giving up. Watch the backtrack counter climb.

Do all engines backtrack?

Java, JavaScript, Python and PCRE do. Engines like RE2 (Go) guarantee linear time by not supporting some features.