Match a whole string against a pattern where . is any one character and * repeats the element before it zero or more times. Every star poses the same question: how many characters should it eat? Trying every answer can take exponential time, while a table of prefix pairs settles it in |s|·|p| steps.
Cell dp[i][j] answers one yes-or-no question: do the first i characters of the string match the first j characters of the pattern? Row 0 is the empty string and column 0 the empty pattern. Each cell reads at most two cells that are already filled, the same idea as the tables in 004 · Dynamic programming. The twist is the star, which can reach two columns back.
How to read this: Down the side: the string. Across the top: the pattern. Each cell answers "does this much of the string match this much of the pattern?" (T = yes, F = no). ε means "nothing yet", the empty start. The bottom-right cell is the final answer.
Try this: Press Step a few times on aab · c*a*b and watch where each cell looks: diagonally, or two columns left at a star.
"One more copy" points straight up and stays in the same column. After the star eats s[i−1], the same x* is still there to eat the characters before it. "Zero copies" jumps two columns left because it drops the whole x* pair at once.
The same rule written top-down: match(i, j) asks whether the rest of the string from position i matches the rest of the pattern from position j. At a star it tries zero copies first, and if that fails it lets the star eat one character and asks again. Without a memo, different choices keep arriving at the same (i, j) and solve it from scratch each time.
How to read this: In the trace, each line is one call; the indent shows how deep the recursion is, and the quoted text is what's left of the string and pattern. In the grid, row = how far into the string, column = how far into the pattern (headers show the next character, ∅ = finished). The number counts calls to that spot; 3F means called 3 times, answer False.
Try this: Run Naive on aaaaaa · a*a*a*b, then switch to Memoized and compare the numbers in the grid.
Take a string of n copies of a and a pattern of a* groups followed by b. The answer is plainly false, since the string has no b. A backtracking matcher can't see that. It tries every way to share the a's among the stars, and each one fails at the b. The chart counts calls on a log scale.
How to read this: Each step up the left axis is 10× more work (10⁶ is a million). The red line climbs steeply; the green one stays nearly flat.
Try this: Drag n to 20 with one per a, then press Time the naive matcher.
The DP table has one cell per (string prefix, pattern prefix) pair, so it never does more than (|s|+1)·(|p|+1) steps no matter how the stars are arranged.
Many regex engines search by backtracking, much like the naive matcher here. Backtracking makes features such as backreferences easy to support, but some patterns make it blow up. This is called catastrophic backtracking, and a pattern or input built to trigger it can stall a server (a ReDoS attack). Backtracking engines add many optimizations, so a given pattern may or may not blow up in a given engine.
Other engines, such as RE2 and Go's regexp, simulate a finite automaton. They track every pattern position that could be active after each character, so the time grows linearly with the text for a fixed pattern. In exchange they leave out backreferences. Each row of the lab 1 table is exactly such a set: the pattern prefixes that the string so far can match.