The idea: does the pattern match the whole text?

A glob pattern, like the *.txt you type in a shell, has two wildcards: ? matches any one character and * matches any run of characters, including none. A simple regex has . for any one character and x* for zero or more copies of x. The question is always about the whole text: does *a*b match adceb? Yes: the first * takes nothing, a takes a, the second * takes dce and b takes b.

The pattern *a*b written over the text adceb: the first star covers nothing, a covers a, the second star covers d c e, and b covers b, so the text splits as '' + a + dce + b.
A match splits the text into pieces, one per pattern part; a star may take an empty piece.

The hard part is the star: it could take 0, 1, 2, … characters, and trying every choice by backtracking can take exponential time. Dynamic programming asks a smaller yes/no question for every pair of prefixes instead, and fills a table of the answers. The page fills that table cell by cell, shows the rule each cell used, and then follows the true cells back to show why the answer is yes.

The table: pattern prefixes × text prefixes

Let the pattern p have m characters (the rows) and the text t have n (the columns). D[i][j] is T when the first i pattern characters match exactly the first j text characters, and F otherwise. The answer is the bottom-right corner D[m][n].

  • Base row: the empty pattern matches only the empty text, so D[0][0] = T and D[0][j] = F for j > 0.
  • Base column: a letter, ? or . needs a character, so D[i][0] stays T only while every piece so far is a star that matches nothing (** in glob, a*b* in regex). (Demo: glob empty text vs **)

One rule per row

Which neighbours a cell looks at depends only on the pattern character of its row. Write c for the text character of the column:

row characterruleD[i][j] is T when
a letter↖ the letter equals cpi = c and D[i-1][j-1]
glob ?, regex .↖ any one characterD[i-1][j-1]
glob *↑ the star is empty, or ← it eats cD[i-1][j] or D[i][j-1]
regex x*↑↑ zero copies of x, or ← one more xD[i-2][j] or (x fits c and D[i][j-1])
Two small grids. Glob star: the cell reads the cell above (star matches nothing) and the cell to its left (star eats the column's character). Regex x star: the cell reads the cell two rows up (zero copies, skipping both the x row and the star row) and the cell to its left, but the left option only counts when x equals the column's character or x is a dot.
A glob * looks up or left; a regex x* looks two rows up or left, and left only counts when x fits.

The "eat one" option is the trick: D[i][j-1] already says the star could cover the text up to j − 1, so letting it cover one more character keeps the match going. A star that eats five characters is five ← steps along its row, not five separate guesses. In the animation the cell being filled has a red ring, the cells it reads are blue, the one that decides is darker blue, and a T cell keeps the arrow of the first rule that made it true. (Demo: glob adceb vs *a*b)

In regex mode the row of the letter x just before a * is filled like any letter row, but the star row never uses it: the pair x* is one piece. That is why c*a*b matches aab: c* takes zero copies (↑↑ from the ε row), a* takes aa, and b takes b. (Demo: regex aab vs c*a*b) A .* eats anything. (Demo: regex ab vs .*)

The proof path

A T in the corner says yes; the arrows say how. Start at D[m][n] and follow each T cell's arrow to the T cell it came from until you reach D[0][0]. A ↖ or ← step uses up one text character and gives it to the pattern piece of that row; ↑ or ↑↑ ends a star's run. Read forward, the path splits the text into one piece per pattern part, which the match panel lists.

When the corner is F there is no path, and the page shows how far the match got instead: in the last row, the text prefixes the whole pattern does match; in the last column, the pattern prefixes that use up the whole text. a*c?b against acdcb: the prefix a*c? already uses up all of acdcb (a, then * takes cd, c, and ? takes b), so the last b has nothing left; and no other split puts c, any, b on the last three letters d c b. (Demo: glob acdcb vs a*c?b) mis*is*p*. against mississippi fails from the other side: no pattern prefix covers the whole text. The pieces m, i, s*, i, s* reach at most mississ, and then p* and one . cannot spell the remaining ippi. The whole pattern matches only the shorter texts missis, mississ and mississi. (Demo: regex mississippi vs mis*is*p*.)

Glob and regex side by side

globsimple regex
any one character?.
repetition* = any run of anythingx* = a run of copies of x
"anything at all"*.*
star with nothing before itfinenot allowed (the page drops it)
where you meet itshell file names, fnmatch, .gitignoregrep, re.fullmatch, LeetCode 10

Running time and memory

There are (m + 1)(n + 1) cells and each reads at most two others, so the table takes Θ(mn) time and space. Each row only needs itself and the row above (two above for regex), so the yes/no answer fits in a few rows of memory; the proof path needs the whole table. Plain backtracking that tries every length for each star can take exponential time on patterns like a*a*a*a*b against a long run of a's; the table never does more than mn work.

See also Regex to NFA to DFA, which handles full regular expressions (with | and grouping) by building an automaton instead of a table, and Edit Distance, another two-string table that is filled from its three neighbours and traced back.

What the page leaves out

Texts and patterns are limited to 12 characters (letters, plus ? * or . *) so the table fits. The page leaves out character classes ([a-z]), escapes, the regex operators +, ?, | and groups, search inside a longer text (instead of a whole match), the greedy two-pointer algorithm for glob patterns, the memoized top-down version of the same recurrence, and how real regex engines (backtracking or automata) do it.