Advanced Regular Expressions
Character classes, quantifiers, anchors, groups and backreferences. Invitational competition topic.
Overview
The FSAs and Regular Expressions topic introduces the core operators (concatenation, union, Kleene star) and the everyday regex additions ?, +, ., [ ] and ( ). This invitational topic adds the rest of the toolkit used by real programming languages: shorthand character classes such as \d and \w, exact repetition counts with { }, anchors that pin a match to the start or end of a line, word boundaries, and backreferences that force part of a string to repeat.
Questions give you a pattern and a list of candidate strings and ask which ones match, or describe a set of strings and ask you to write a pattern. The skill is reading a dense pattern piece by piece and testing each candidate methodically.
Key Concepts:
- A backslash turns a letter into a character class (
\d,\w,\s) or turns a special symbol into a literal (\.,\*). - Uppercase versions negate:
\Dis anything that is not a digit. ^and$anchor the pattern to the beginning and end of the string; without them a pattern may match anywhere inside a longer string.- Parentheses capture what they match, and
\1,\2, ... refer back to those captures.
Key Concepts
Useful Patterns
| Pattern | Meaning | Example regex | Matches | Does not match |
|---|---|---|---|---|
\d | Any digit; same as [0-9] | \d\d\d | 123 | 1-3 |
\D | Any character that is not a digit | \d\D\d | 1-3 | 123 |
\w | Word character: letter, digit or underscore; same as [a-zA-Z0-9_] | \w\w\w | a_A | a-A |
\W | Any character that is not a word character | \W\W\W | +-$ | +_@ |
\s | Whitespace: space, tab or line break | \d\s\w | 1 a | 1ab |
\S | Any character that is not whitespace | \w\w\w\w\S\d | Test#1 | test 1 |
\b | Word boundary: the position between a word character and a non-word character (or the start/end of the string) | \bis\b | is; (the word "is") | This island |
{n}, {min,}, {min,max} | Repeat the preceding element exactly n times, at least min times, or between min and max times | abc{2} | abcc | abc |
.* | Zero or more of any character | .* | abbb, the empty string | |
.+ | One or more of any character | .+ | a, abbcc | the empty string |
^ | Anchor: the start of the string | ^The\s\w+ | The contest | One contest |
$ | Anchor: the end of the string | \d{4}\sACSL$ | 2020 ACSL | 2020 STAR |
\ | Escape: match a special character literally | \w\w\w\. | cat. | lion |
( ) | Group and capture | ^(file.+)\.docx$ | file_graphs.docx | data.docx |
\1, \2 | Backreference: repeat exactly what group 1 (or 2) captured | r(\w)g\1x | regex (group 1 is e) | regxx |
Reading a Pattern
- Split the pattern into tokens: each character class, literal, group and quantifier.
- Note which quantifier belongs to which token.
\d{3}is three digits;(ab){2}is "abab". - Check for anchors. With
^...$the whole string must be consumed; otherwise the pattern only has to appear somewhere in the string. - For backreferences, write down what each group captured for the specific string, then check that the later text is identical (including case).
- Test every candidate string against every token, in order. Reject as soon as one token cannot be satisfied.
Backreferences in Detail
Groups are numbered by the position of their opening parenthesis, left to right. In (\d\d)\+(\d\d)=\2\+\1, group 1 is the first two digits and group 2 the second two. The string 20+21=21+20 matches because after the equals sign the text is group 2 then group 1. The string 20+21=20+21 does not, because the order is wrong. Backreferences must match the captured text, not just the same kind of text: if group 1 captured "e", \1 matches only "e".
Examples
Which of these strings match ^w{3}\.([a-z0-9]([-a-z0-9]{0,61}[a-z0-9])+\.)+[a-z0-9][-a-z0-9]{0,61}[a-z0-9]?
- www.google.com
- www.-petsmart.com
- www.edu-.ro
- www.google.co.in
- www.examples.c.net
- www.edu.training.computer-science.org
- www.everglades_holidaypark.com
Take the pattern apart:
^w{3}\.: the string starts with exactly "www" and a literal dot.([a-z0-9]([-a-z0-9]{0,61}[a-z0-9])+\.)+: one or more domain labels, each followed by a dot. A label starts with a lowercase letter or digit, may contain hyphens in the middle, ends with a letter or digit, and is at least 2 characters long (the inner group must appear at least once and itself ends with a letter or digit).[a-z0-9][-a-z0-9]{0,61}[a-z0-9]: the final top-level label, with the same rules and no trailing dot.
String 2 has a label starting with a hyphen, string 3 has a label ending with a hyphen, string 5 has the one-character label "c", and string 7 contains an underscore, which is not allowed.
Matches: 1, 4 and 6
Describe strings that: contain only lowercase letters and the character "."; start and end with the same letter; and consist of one to three vowels, then zero or more dots, then at least one consonant, between those matching end letters.
([a-z])captures the first letter as group 1.[aeiou]{1,3}matches one to three vowels.\.*matches zero or more literal dots (the backslash is needed because a bare dot means "any character").[b-df-hj-np-tv-z]+matches one or more consonants. The ranges skip over each vowel.\1requires the string to end with the same letter that group 1 captured.
Pattern: ([a-z])[aeiou]{1,3}\.*[b-df-hj-np-tv-z]+\1
Which strings contain a match for \bcat\b? "the cat sat" does, because "cat" is surrounded by spaces. "cat's" does, because the apostrophe is a non-word character, so there is a boundary after the t. "concatenate" and "bobcat" do not, because the letters on either side of "cat" are word characters, so there is no boundary.
Practice Problems
Enter the numbers of the matching strings separated by commas, for example 1,3,5. Every pattern below is anchored with ^ and $ unless stated otherwise, so the whole string must match.
Problem 1 Junior
Which of the following strings match the pattern ^\d{3}-\d{4}$?
- 555-1234
- 5551234
- 55-12345
- 123-4567
- 123-45678
Solution
The pattern is exactly three digits, a hyphen, exactly four digits, and nothing else.
- 555-1234: 3 digits, hyphen, 4 digits. Matches.
- 5551234: no hyphen. No match.
- 55-12345: only 2 digits before the hyphen and 5 after. No match.
- 123-4567: 3 digits, hyphen, 4 digits. Matches.
- 123-45678: 5 digits after the hyphen; the
$anchor rejects the extra digit. No match.
Matches: 1, 4
Problem 2 Junior
Which of the following strings match the pattern ^[A-Z]\w+\s\d+$?
- Room 101
- room 7
- A1 22
- Hall_B 3
- Room101
Solution
One uppercase letter, then one or more word characters, then one whitespace character, then one or more digits.
- Room 101: R, "oom", space, 101. Matches.
- room 7: starts with a lowercase letter. No match.
- A1 22: A, "1" (a digit is a word character), space, 22. Matches.
- Hall_B 3: H, "all_B" (underscore is a word character), space, 3. Matches.
- Room101: there is no whitespace, so
\scannot be satisfied. No match.
Matches: 1, 3, 4
Problem 3 Intermediate
Which of the following strings match the pattern ^(\w+)\s\1$?
- ha ha
- ha haha
- go Go
- 22 22
- hi_hi hi_hi
Solution
Group 1 captures a word; after a single space the string must end with exactly that same word.
- ha ha: group 1 = "ha", followed by "ha". Matches.
- ha haha: group 1 = "ha", but the rest is "haha", not "ha". No match.
- go Go: group 1 = "go", but "Go" differs in case. Backreferences are exact. No match.
- 22 22: digits are word characters; group 1 = "22", repeated. Matches.
- hi_hi hi_hi: underscores are word characters; group 1 = "hi_hi", repeated. Matches.
Matches: 1, 4, 5
Problem 4 Intermediate
The pattern \bcat\b is not anchored. Which of the following strings contain a match for it?
- cat
- concatenate
- the cat sat
- cat's
- bobcat
Solution
\b matches the position between a word character and a non-word character (or the edge of the string). The pattern therefore matches "cat" only as a whole word.
- cat: boundaries at both ends of the string. Matches.
- concatenate: "cat" is preceded by n and followed by e, both word characters, so there is no boundary on either side. No match.
- the cat sat: "cat" is surrounded by spaces. Matches.
- cat's: boundary at the start, and the apostrophe after t is a non-word character, so there is a boundary there too. Matches.
- bobcat: preceded by b, a word character, so no boundary before c. No match.
Matches: 1, 3, 4
Problem 5 Senior
Which of the following strings match the pattern ^(\w)(\w)\w*\2\1$?
- abccba
- abba
- abab
- xy12yx
- aaa
- a-bb-a
Solution
Group 1 is the first character and group 2 the second. After any number of word characters, the string must end with group 2 followed by group 1. In other words: the last two characters are the first two reversed, and everything is a word character. The string must be at least 4 characters long.
- abccba: groups a, b; middle "cc"; ends "ba". Matches.
- abba: groups a, b; middle is empty (
\w*allows zero); ends "ba". Matches. - abab: groups a, b; would need to end "ba" but ends "ab". No match.
- xy12yx: groups x, y; middle "12"; ends "yx". Matches.
- aaa: groups a, a; the ending "aa" needs two more characters but only one remains. No match.
- a-bb-a: the hyphen is not a word character, so
(\w)fails at position 2. No match.
Matches: 1, 2, 4