Capturing groups and backreferences in PHP - Time & Space Complexity

Time Complexity: Capturing groups and backreferences

O(n)

Understanding Time Complexity

When using capturing groups and backreferences in PHP regular expressions, it's important to understand how the matching process grows as the input gets bigger.

We want to know how the time to find matches changes when the input string or pattern size increases.

Scenario Under Consideration

Analyze the time complexity of the following PHP code using capturing groups and backreferences.

$pattern = '/(\w+)\s\1/';
$input = 'word word word word word word word word word word';
if (preg_match($pattern, $input, $matches)) {
    echo "Match found: " . $matches[0];
} else {
    echo "No match found.";
}
    

This code looks for two identical words next to each other using a capturing group and a backreference.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine tries to match the pattern at each position in the input string.
• How many times: It attempts matching starting from each character in the input until a match is found or input ends.

How Execution Grows With Input

As the input string gets longer, the regex engine tries more starting points to find the pattern.

Input Size (n)	Approx. Operations
10	About 10 attempts to match
100	About 100 attempts to match
1000	About 1000 attempts to match

Pattern observation: The number of attempts grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a match grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "Backreferences always make regex run in constant time."

[OK] Correct: Backreferences can cause the regex engine to try many positions, so time usually grows with input size, not stay fixed.

Interview Connect

Understanding how capturing groups and backreferences affect performance helps you write efficient patterns and explain your code clearly in interviews.

Self-Check

"What if we changed the pattern to use nested capturing groups with backreferences? How would the time complexity change?"

Practice

1. What does a capturing group in a PHP regular expression do?

easy

A. It ignores the matched text inside parentheses.

B. It repeats the entire pattern multiple times.

C. It saves part of the matched text for later use.

D. It changes the case of matched text.

Solution

1. Step 1: Understand capturing groups

   Parentheses () in regex save the matched part for reuse.

2. Step 2: Purpose of capturing groups

   This saved part can be accessed later in the code or reused in the pattern.

3. Final Answer:

   It saves part of the matched text for later use. -> Option C

4. Quick Check:

   Capturing group = save matched text [OK]

Hint: Parentheses capture text to reuse later in regex or code [OK]

Common Mistakes:

• Thinking capturing groups repeat patterns
• Believing they ignore matched text
• Assuming they change text case

2. Which of the following is the correct syntax for a backreference to the first capturing group in a PHP regex pattern?

easy

A. \(1\)

B. \\1

C. \$1

D. \1

Solution

1. Step 1: Identify backreference syntax in PHP regex

   Backreferences use a single backslash followed by group number, like \1 in regex patterns.

2. Step 2: Differentiate from string escaping

   In PHP strings, to represent \1 you write "\\1" but the regex pattern itself uses \1.

3. Final Answer:

   \1 -> Option D

4. Quick Check:

   Backreference first group = \1 [OK]

Hint: Use single backslash before group number for backreference in regex [OK]

Common Mistakes:

• Using double backslash instead of single
• Confusing backreference with variable syntax
• Adding parentheses around the number

3. What will be the output of the following PHP code?

$pattern = '/(\w+)\s\1/';
$subject = 'hello hello world';
if (preg_match($pattern, $subject, $matches)) {
    echo $matches[0];
} else {
    echo 'No match';
}

medium

A. hello world

B. hello hello

C. No match

D. hello

Solution

1. Step 1: Understand the regex pattern

   The pattern /(\w+)\s\1/ matches a word, a space, then the same word again (backreference \1).

2. Step 2: Apply pattern to the subject string

   The string 'hello hello world' contains 'hello hello' which matches the pattern.

3. Final Answer:

   hello hello -> Option B

4. Quick Check:

   Backreference matches repeated word = hello hello [OK]

Hint: Backreference \1 matches exact previous captured word [OK]

Common Mistakes:

• Ignoring backreference meaning
• Matching different words instead of repeated
• Expecting full string match

4. Identify the error in this PHP regex pattern: preg_match('/(\d+)\s\2/', '123 123', $matches);

medium

A. Backreference \2 is invalid because only one group is captured.

B. The pattern should use \1 instead of \2 for backreference.

C. The pattern is missing delimiters.

D. The pattern should not use capturing groups.

Solution

1. Step 1: Count capturing groups in the pattern

   There is only one capturing group: (\d+), so only \1 is valid.

2. Step 2: Check backreference usage

   Using \2 refers to a second group which does not exist, causing an error.

3. Final Answer:

   Backreference \2 is invalid because only one group is captured. -> Option A

4. Quick Check:

   Backreference number must match captured groups [OK]

Hint: Backreference number must not exceed captured groups count [OK]

Common Mistakes:

• Using backreference number higher than groups
• Ignoring missing groups
• Confusing delimiters with backreferences

5. Given the string 'abc123abc456', which regex pattern using capturing groups and backreferences will match the repeated substring 'abc' only if it appears twice separated by digits?

hard

A. /(abc)\d+\1/

B. /(abc)\1\d+/

C. /abc(\d+)abc/

D. /(abc)+\d+/

Solution

1. Step 1: Understand the requirement

   We want to match 'abc' repeated twice with digits in between.

2. Step 2: Analyze each pattern

   /(abc)\d+\1/: /(abc)\d+\1/ matches 'abc', digits, then same 'abc' again. This fits the requirement.
   /(abc)\1\d+/: /(abc)\1\d+/ expects 'abcabc' then digits, which is incorrect.
   /abc(\d+)abc/: /abc(\d+)abc/ matches 'abc', digits, 'abc' but digits are captured, not 'abc'.
   /(abc)+\d+/: /(abc)+\d+/ matches one or more 'abc' then digits, but no backreference to ensure repetition.

3. Final Answer:

   /(abc)\d+\1/ -> Option A

4. Quick Check:

   Backreference \1 repeats captured 'abc' after digits [OK]

Hint: Backreference \1 repeats first group exactly where needed [OK]

Common Mistakes:

• Placing backreference before digits
• Not using backreference to repeat 'abc'
• Capturing digits instead of 'abc'