Regular expression and wildcard matching

Why this matters

A pattern is a short description of many strings at once. Search tools use patterns to find log lines that look like a timestamp. Web frameworks use them to match a route such as /users/42 against a rule. Programming languages call their pattern language regular expressions, usually shortened to regex.

A full regex language has many features. This lesson covers the smallest version that still shows the whole method. It has two special symbols: a dot that matches any one character, and a star that repeats the character before it zero or more times. The method is dynamic programming, the technique from the earlier lessons in this module. You split the question into smaller questions, answer each small question once, and store the answers in a table. The table has one cell for every pair of a text prefix and a pattern prefix.

The title also mentions wildcard matching. Exercise 6 in the Practice section shows the wildcard rules. The table method is the same, only the star changes meaning.

Words you will need

• Text: the string you test. In the examples below, the text is aab.
• Pattern: the string of rules you test the text against. In the examples below, the pattern is c*a*b.
• Match: the whole text fits the whole pattern. A pattern that matches only the start of the text does not count.
• Dot: the symbol . in a pattern. It matches any one character.
• Star: the symbol * in a pattern. Here a star always comes right after a letter or a dot. The pair x* means zero or more copies of x.
• Zero copies: the star matches nothing at all, so the pair x* disappears from the match.
• Prefix: the first few characters of a string. The prefixes of aab are the empty string "", then a, then aa, then aab.
• Empty string: a string with no characters, written "".
• Table: a grid of rows and columns. In C++ it is a std::vector of std::vector of bool.
• Base case: an answer that you write down directly, without computing it from other cells.

Two rules, with examples

Start with five small examples. Each row of the table below says whether the pattern matches the whole text.

Two facts come out of these examples. A star never stands alone. It always attaches to the character in front of it, so the pattern *a is not allowed. A star can also match nothing, which is why a*b matches the single letter b.

The dot works like a wildcard for one character. The pattern a.c matches abc and axc, but not ac, because the dot must match a real character.

Before writing any code, decide what the table means. Let the text have n letters and the pattern have m characters. The table has n + 1 rows and m + 1 columns. The cell in row i and column j answers this question:

Do the first i letters of the text match the first j characters of the pattern?

The answer is either true or false. The final answer to the whole problem is the cell in the last row and last column.

The idea: fill the table from the top left

Row 0 means "the text has no letters yet". Column 0 means "the pattern has no characters yet". Both start with the empty string, so they are the base cases. The table below is real output from a debug print of the same cell rules as Program 1, for the text aab and the pattern c*a*b. Row - is the empty text, and column - is the empty pattern. T means true and . means false.

       - c * a * b
  -    T . T . T .
  a    . . . T T .
  a    . . . . T .
  b    . . . . . T

Read the first row. The cell under * after c is T, because c* can match the empty text. The cell under the second * is also T, because c*a* can match the empty text too. The cell under b is ., because b needs a real b in the text.

Read the second row, which uses the first letter a of the text. The cell under a is T. It means that c*a matches the text a, where c* took zero copies and the a matched the a. The cell under the second star is T because the star can also take the same a as one copy.

The bottom-right cell is T. The text aab matches the pattern c*a*b completely, which is the answer.

Base cases: the empty text and the empty pattern

Two base cases fill the first row and the first column, and both are easy to get wrong.

The first base case is one cell. dp[0][0] is true, because the empty text matches the empty pattern. Nothing has to be matched, so nothing can go wrong.

The second base case is the first row, which is the empty text against a pattern. A pattern can match the empty text only when every character in it can vanish. A plain letter or dot cannot vanish, but a letter followed by a star can, because the star takes zero copies. So the rule is:

• If the pattern character at column j is a star, then dp[0][j] equals dp[0][j - 2]. The star and the letter before it disappear together.
• Otherwise dp[0][j] is false.

Here are two patterns against the empty text. The pattern a*b* matches "", because both pairs a* and b* can vanish. The pattern a*b does not match "", because the plain b at the end cannot vanish.

The first row of the table for a*b* against the empty text is T . T . T. The cell after a is . because a single a cannot match nothing. The cell after a* is T. The cell after b is .. The cell after b* is T, and that last column is the one the pattern needs.

The first column needs no special rule. For any text with at least one letter, the empty pattern matches nothing, so every cell dp[i][0] for i >= 1 is false. The loop fills those cells automatically.

The two cases for every other cell

Now look at a cell dp[i][j] with i >= 1 and j >= 1. The text letter just added is s[i - 1], and the pattern character at column j is p[j - 1]. The code has to handle two situations.

Case A: the pattern character is a letter or a dot. Then the new text letter must match it. "Match" means the two are equal, or the pattern character is a dot. The earlier part of the text must also match the earlier part of the pattern. So:

dp[i][j] = (p[j - 1] matches s[i - 1]) and dp[i - 1][j - 1]

Case B: the pattern character is a star. The star belongs to the character in front of it, which is p[j - 2]. There are two choices.

• The star takes zero copies. The pair x* disappears, so the answer is the cell two columns to the left: dp[i][j - 2].
• The star takes one more copy. The new text letter must match x, and the star stays in place for the next letter. The answer is the cell in the row above, in the same column: dp[i - 1][j].

The second choice uses the row above and not the row above one column to the left. That is the point of the star. It keeps absorbing letters, so the pattern position does not move on.

Put the star rule in one place:

if p[j - 1] is a star:
    dp[i][j] = dp[i][j - 2]                          the star takes zero copies
            or (p[j - 2] matches s[i - 1]
                and dp[i - 1][j])                    the star takes one more copy
else:
    dp[i][j] = (p[j - 1] matches s[i - 1]) and dp[i - 1][j - 1]

Worked example: aa against a*

Fill the table for the text aa and the pattern a*. The table has three rows and three columns.

Start with the base cases. dp[0][0] is true. The pattern position 2 holds the star, so dp[0][2] is dp[0][0], which is true. The empty text matches a*.

Next, the first text letter a, which is row 1.

• Column 1, the letter a of the pattern. The letter matches the text a, and dp[0][0] is true. So dp[1][1] is true.
• Column 2, the star. Zero copies gives dp[1][0], which is false. One more copy works because a matches the text letter a, and dp[0][2] is true. So dp[1][2] is true.

Next, the second text letter a, which is row 2.

• Column 1. The letter matches the second a, and dp[1][0] is false. So dp[2][1] is false.
• Column 2, the star. Zero copies gives dp[2][0], which is false. One more copy works because a matches the second a, and dp[1][2] is true. So dp[2][2] is true.

The answer is dp[2][2], which is true. The star took one copy for each letter of the text.

Program 1: the matcher

This program implements the rules above and checks the examples from the lesson. It keeps the same two-dimensional vector<vector<bool>> table for every pair of prefixes. The validity check at the start rejects a star at the beginning of the pattern or a star after another star. Those patterns have no meaning in this lesson's rules.

#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>
 
// Returns true when the whole text s matches the pattern p.
// '.' matches any one character.
// 'x*' matches zero or more characters x, where x is any letter or '.'.
bool isMatch(std::string_view s, std::string_view p) {
    const std::size_t n = s.size();
    const std::size_t m = p.size();
 
    // A '*' must follow a letter or '.', never the start of the pattern or another '*'.
    for (std::size_t j = 0; j < m; ++j) {
        if (p[j] == '*' && (j == 0 || p[j - 1] == '*')) {
            throw std::invalid_argument("'*' must follow a letter or '.'");
        }
    }
 
    // dp[i][j] is true when the first i characters of s match the first j characters of p.
    std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(m + 1, false));
 
    // Empty base: an empty text matches an empty pattern.
    dp[0][0] = true;
 
    // Empty text: a pattern can match it only if every letter in it is followed by '*',
    // so the star can take zero copies. "a*b*" matches the empty text, "a*b" does not.
    for (std::size_t j = 2; j <= m; ++j) {
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
 
    for (std::size_t i = 1; i <= n; ++i) {
        for (std::size_t j = 1; j <= m; ++j) {
            const char pc = p[j - 1];
            if (pc == '*') {
                // The star belongs to the letter before it, p[j - 2].
                const char letter = p[j - 2];
                // Case 1: the star takes zero copies, so drop "x*" from the pattern.
                dp[i][j] = dp[i][j - 2];
                // Case 2: the star takes one more copy, which must match s[i - 1].
                // The star stays on the same pattern position for the next character.
                if ((letter == '.' || letter == s[i - 1]) && dp[i - 1][j]) {
                    dp[i][j] = true;
                }
            } else {
                // A normal letter or '.' must match s[i - 1], and the rest must match.
                if ((pc == '.' || pc == s[i - 1]) && dp[i - 1][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
    }
    return dp[n][m];
}
 
int main() {
    struct Case {
        std::string_view s;
        std::string_view p;
    };
    const std::vector<Case> cases = {
        {"aa", "a"},
        {"aa", "a*"},
        {"ab", ".*"},
        {"aab", "c*a*b"},
        {"mississippi", "mis*is*p*."},
        {"aaa", "a*a"},
        {"", "a*b*"},
        {"", "a*b"},
    };
    for (const auto& c : cases) {
        std::cout << '"' << c.s << "\" vs \"" << c.p << "\" -> "
                  << (isMatch(c.s, c.p) ? "true" : "false") << '\n';
    }
    return 0;
}

Compile and run it with the standard flags:

g++ -std=c++20 -Wall -Wextra -o regex_match regex_match.cpp
./regex_match

The output is:

"aa" vs "a" -> false
"aa" vs "a*" -> true
"ab" vs ".*" -> true
"aab" vs "c*a*b" -> true
"mississippi" vs "mis*is*p*." -> false
"aaa" vs "a*a" -> true
"" vs "a*b*" -> true
"" vs "a*b" -> false

The compile line printed no warnings. Each output line matches the examples above.

Two results need a short explanation. mississippi does not match mis*is*p*., because the pattern ends with one dot, which matches exactly one letter. No choice of star copies lets the rest of the text fit in front of that dot, so the match fails. The other surprise is "" vs "a*b*", which is true only because of the empty-text base row.

The table has (n + 1) * (m + 1) cells, and each cell does a fixed amount of work. So the time and the memory both grow with the product of the two lengths.

Second example: ab against .*

The pattern .* means "any number of any characters". For the text ab, the dot matches a and the star repeats the dot to match b. The column for .* is T in every row, including row 0, so the final cell dp[2][2] is true.

This is the pattern to remember for many search boxes. A pattern such as .*error.* matches any line that contains the word error, because each .* absorbs the characters on its side.

Third example: aaa against a*a

This example shows the star taking a middle number of copies. The text has three a letters, and the pattern is a* followed by one more a.

The star must take two copies and leave one a for the final pattern letter. The table finds this path without being told. In row 3, column 3 (the final a), the cell reads from row 2, column 2. Row 2, column 2 is true because the star took the first two copies. So row 3, column 3 is true.

A different way to see it: the pattern has a minimum length. The star can take zero copies, so the pattern can match texts of length one or more. The text of length three is long enough, so the question is only whether the star can absorb the extra letters. It can, since every letter is an a.

Common mistakes

Only the zero-copies choice for a star. A matcher that drops x* but never lets the star take a letter returns the wrong answer for aa against a*. The output below comes from a variant of Program 1 that keeps the zero-copies case and removes the one-more-copy case.

noOneMore(aa, a*) = 0

The correct answer is true. The fix is the second if in the star branch, the one that checks dp[i - 1][j].

Forgetting the empty-text row. If the first row is left as false for every column after 0, then a pattern made only of star pairs fails against the empty text. The output below comes from a variant of Program 1 that skips the row.

noEmptyBase("", a*) = 0
noEmptyBase("", a*b*) = 0

The correct answer for a*b* is true. The fix is the loop that sets dp[0][j] from dp[0][j - 2].

Reading the letter in front of a star when there is none. When the column j is 1, the letter before the star is at index j - 2, which is -1. An unsigned index does not go below zero. It wraps around to a huge number, and at() reports that the index is out of range. Here is the real output of a program that reads p.at(j - 2) with j = 1:

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string_view::at: __pos (which is 18446744073709551615) >= this->size() (which is 3)

The validity check at the top of Program 1 avoids this case. A pattern that starts with a star is rejected before the table is built, with a clear message.

Using shell wildcard rules for a star. In the shell, * matches any run of characters in a file name. In this lesson, a star belongs to the character in front of it. The pattern *c has no letter before its star, so it is not valid here. The program reports it like this:

terminate called after throwing an instance of 'std::invalid_argument'
  what():  '*' must follow a letter or '.'

If you need the shell rules, see the wildcard exercise in the Practice section.

Mixing up rows and columns. Row i counts text letters and column j counts pattern characters. Swapping them reads s[i] where p[j] is meant, and the program can crash or give a wrong answer. Keep the names i and j tied to s and p in your head while you write the loops.

Practice

Exercise 1. Does the pattern a.*c* match the text ab? Work out the answer, then check it.

Show the answer

Yes. The a matches the first letter. The .* takes b as one copy of the dot. The c* takes zero copies. Calling isMatch on these inputs returns true.

Exercise 2. For the pattern x*y, which of these texts match: y, xxy, and xxz?

Show the answer

y matches, because x* takes zero copies. xxy matches, because x* takes two copies. xxz does not match, because the last letter must be y. Calling isMatch on the three texts gives true, true and false.

Exercise 3. Does the pattern a* match the text b? Explain why in one sentence.

Show the answer

No. The star repeats only the letter a, so it can take zero copies or any number of a letters. The text b is one letter, which is neither zero copies of a nor an a. isMatch returns false.

Exercise 4. Does the pattern ab*a*c*a match the text aaa? Say how many copies each star takes.

Show the answer

Yes. The first a matches the first letter, b* takes zero copies, a* takes the second letter, c* takes zero copies, and the last a matches the third letter. isMatch returns true.

Exercise 5. The time and memory cost of the table depends on the lengths of the text and the pattern. Give the number of cells in the table and the number of steps for each cell.

Show the answer

With a text of length n and a pattern of length m, the table has (n + 1) * (m + 1) cells. Each cell takes a fixed number of steps, so the total time is proportional to n * m. The memory for the table is also proportional to n * m, here one bool per cell, though vector<bool> stores each one in a single bit.

Exercise 6. Wildcard matching uses ? to match any one letter, and * to match any run of letters, including an empty run. The star no longer belongs to a letter in front of it. Write the recurrence for the star cell dp[i][j], and check it against the cases aa with * and b with a*.

Show the answer

The star takes an empty run or it takes one more letter, so the cell reads:

dp[i][j] = dp[i][j - 1]  or  dp[i - 1][j]

The first term means the star matches the empty run, so the pattern is the one before the star. The second term means the star absorbs the new letter, so the same pattern position still applies to the row above. For aa against *, the answer is true, because the star takes the whole text. For b against a*, the answer is false, because the letter a does not match b. A Python check of the wildcard recurrence against fnmatch on 20,000 random cases gave no mismatches.

Summary

• A table cell dp[i][j] answers whether the first i letters of the text match the first j characters of the pattern.
• The empty text matches an empty pattern, and a pattern can match the empty text only when its stars cover every letter.
• A plain letter or dot matches only the new text letter, and it must agree with the cell diagonally above and to the left.
• A star either takes zero copies, which looks two columns left, or takes one more copy, which looks at the row above in the same column.
• Check the empty-text row and the star rules first. Most wrong answers come from those two places.