wildcard

Your mission

Match text against a pattern where * means any run of characters, in a single linear scan.

today's brief

July 2, 2019. Cloudflare deploys one new firewall rule. Buried in it is a regular expression that backtracks catastrophically, and since the firewall runs on every single request before anything else, CPUs across the whole network jump to 100 percent. For 27 minutes a large slice of the web, Discord and Shopify included, just returns errors. The lesson: match in linear time, never explode. Build the matcher that scans once.

See it in action

wildcard_match("a*c", "abc")

Expected result

Your checklist

For your own tracking. Tests grade your code.

* in the pattern matches any sequence of characters, including an empty one.
Every other character in the pattern must match the character at that spot in text.
Return 1 if the whole pattern matches the whole text, otherwise return 0.

More examples

wildcard_match("a*c", "abd")

Expected result

wildcard_match("*=*", "key=val")

Expected result

Constraints

Expected files

match.c

Allowed functions

None. Write every helper yourself.

Back to compete

Solutions

wildcard

Your mission

Match text against a pattern where * means any run of characters, in a single linear scan.

today's brief

See it in action

wildcard_match("a*c", "abc")

Expected result

Your checklist

For your own tracking. Tests grade your code.

* in the pattern matches any sequence of characters, including an empty one.
Every other character in the pattern must match the character at that spot in text.
Return 1 if the whole pattern matches the whole text, otherwise return 0.

More examples

wildcard_match("a*c", "abd")

Expected result

wildcard_match("*=*", "key=val")

Expected result

Constraints

Expected files

match.c

Allowed functions

None. Write every helper yourself.

Back to compete

Solutions