Lookahead and lookbehind in PHP - Time & Space Complexity

Time Complexity: Lookahead and lookbehind

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a PHP regex with lookahead and lookbehind changes as the input grows.

How does the pattern matching cost grow when using these special checks?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "abc123xyz456";
$pattern = '/(?<=\D)\d+(?=\D)/';
preg_match_all($pattern, $string, $matches);

// This finds numbers surrounded by non-digits.

This code uses lookbehind and lookahead to find numbers that have non-digit characters before and after them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine scans the string character by character to check for matches.
• How many times: It checks each position in the string once, applying lookbehind and lookahead at each step.

How Execution Grows With Input

As the string gets longer, the regex engine does more checks, roughly one per character.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows linearly as the string gets longer.

Common Mistake

[X] Wrong: "Lookahead and lookbehind make regex run much slower, like exponentially slower."

[OK] Correct: While these checks add some work, they only look at fixed positions around each character, so the overall time still grows linearly with input size.

Interview Connect

Understanding how regex features like lookahead and lookbehind affect performance helps you write efficient pattern matching in real projects and interviews.

Self-Check

"What if the lookbehind pattern was variable length instead of fixed length? How would the time complexity change?"

Practice

1. What does a positive lookahead (?=pattern) do in PHP regular expressions?

easy

A. Matches the pattern and consumes it in the string

B. Checks if the specified pattern precedes the current position and includes it in the match

C. Checks if the specified pattern follows the current position without including it in the match

D. Checks if the pattern is anywhere in the string regardless of position

Solution

1. Step 1: Understand lookahead behavior

   A positive lookahead (?=pattern) checks if the pattern appears immediately after the current position without consuming characters.

2. Step 2: Compare options with definition

   Checks if the specified pattern follows the current position without including it in the match correctly describes this behavior. Options B and C incorrectly describe lookbehind or normal matching. Checks if the pattern is anywhere in the string regardless of position is too broad.

3. Final Answer:

   Checks if the specified pattern follows the current position without including it in the match -> Option C

4. Quick Check:

   Positive lookahead = check after position [OK]

Hint: Lookahead checks after current spot without consuming [OK]

Common Mistakes:

• Confusing lookahead with lookbehind
• Thinking lookahead consumes characters
• Assuming it matches anywhere, not just after position

2. Which of the following is the correct syntax for a negative lookbehind in PHP regex?

easy

A. (?pattern)

B. (?<=pattern)

C. (?!pattern)

D. (?=pattern)

Solution

1. Step 1: Recall lookbehind syntax

   Negative lookbehind in PHP regex is written as (?<!pattern), which asserts that the pattern does NOT appear before the current position.

2. Step 2: Match options to syntax

   (?

3. Final Answer:

   (?<!pattern) -> Option A

4. Quick Check:

   Negative lookbehind = (?<!pattern) [OK]

Hint: Lookbehind uses (?<=) or (?), negative has exclamation [OK]

Common Mistakes:

• Mixing lookahead and lookbehind syntax
• Using wrong brackets or missing exclamation mark
• Confusing negative and positive forms

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

$text = "apple pie";
if (preg_match('/apple(?= pie)/', $text)) {
    echo "Match found";
} else {
    echo "No match";
}

medium

A. Empty output

B. Match found

C. Syntax error

D. No match

Solution

1. Step 1: Understand the regex pattern

   The pattern /apple(?= pie)/ matches 'apple' only if it is immediately followed by ' pie' without including ' pie' in the match.

2. Step 2: Check the input string

   The string is "apple pie", so 'apple' is followed by ' pie'. The lookahead condition is true, so the match succeeds.

3. Final Answer:

   Match found -> Option B

4. Quick Check:

   Lookahead confirms 'apple' before ' pie' = Match found [OK]

Hint: Lookahead checks next chars without consuming [OK]

Common Mistakes:

• Thinking lookahead consumes characters
• Assuming no match because ' pie' is not part of match
• Confusing output with syntax error

4. Identify the error in this PHP regex using lookbehind:

$text = "hello world";
if (preg_match('/(?

medium

A. No error, code runs fine

B. Lookbehind syntax is incorrect, missing brackets

C. Lookbehind must be at the end of the pattern

D. Lookbehind pattern is fixed width but 'hello' is variable length

Solution

1. Step 1: Check lookbehind syntax and pattern

   The lookbehind (?<!hello) is valid because 'hello' is fixed length (5 characters), which PHP supports.

2. Step 2: Analyze the string and pattern match

   The string is "hello world". The lookbehind asserts 'world' is NOT preceded by 'hello'. Here, 'world' is preceded by 'hello', so the match fails and "No match" is printed.

3. Final Answer:

   No error, code runs fine -> Option A

4. Quick Check:

   Lookbehind syntax correct, no error [OK]

Hint: Lookbehind must be fixed width, 'hello' is fixed length [OK]

Common Mistakes:

• Thinking 'hello' is variable length
• Assuming lookbehind syntax is wrong
• Expecting match when lookbehind condition fails

5. You want to match all occurrences of the word 'cat' only if it is NOT preceded by 'wild' and is immediately followed by 's' in a string. Which regex pattern correctly uses lookahead and lookbehind in PHP?

hard

A. /(?<=wild )cat(?=s)/

B. /(?<=wild)cat(?=s)/

C. /(?wild)cat(?= s)/

D. /(?wild )cat(?=s)/

Solution

1. Step 1: Understand the requirements

   We want 'cat' that is NOT preceded by 'wild ' (note the space) and IS followed immediately by 's'.

2. Step 2: Analyze each option

   /(?(?<!wild ) to exclude 'wild ' before 'cat' and positive lookahead (?=s) to ensure 'cat' is followed by 's'. This matches the requirement.
   /(?<=wild )cat(?=s)/ uses positive lookbehind, which requires 'wild ' before 'cat', opposite of requirement.
   /(?/(?<=wild)cat(?=s)/ uses positive lookbehind without space, which is incorrect.

3. Final Answer:

   /(?<!wild )cat(?=s)/ -> Option D

4. Quick Check:

   Negative lookbehind + positive lookahead = /(?

Hint: Negative lookbehind excludes prefix, positive lookahead confirms suffix [OK]

Common Mistakes:

• Forgetting space after 'wild' in lookbehind
• Using positive lookbehind instead of negative
• Adding space in lookahead incorrectly