String search functions (strpos, strstr) in PHP - Time & Space Complexity

Time Complexity: String search functions (strpos, strstr)

O(n*m)

Understanding Time Complexity

When we use string search functions like strpos or strstr, we want to know how long they take as the string gets bigger.

We ask: How does the time to find a substring grow when the string length grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "Hello, this is a simple example string.";
$search = "simple";
$pos = strpos($string, $search);
if ($pos !== false) {
    echo "Found at position: $pos";
} else {
    echo "Not found.";
}
    

This code looks for the position of a smaller string inside a bigger string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each character in the main string to see if the search string starts there.
• How many times: Up to once for each character in the main string until the substring is found or the string ends.

How Execution Grows With Input

As the main string gets longer, the function may check more characters to find the substring.

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

Pattern observation: The number of checks grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n*m)

This means the time to find the substring grows roughly in proportion to the product of the length of the main string (n) and the length of the substring (m).

Common Mistake

[X] Wrong: "String search is always instant, no matter how long the string is."

[OK] Correct: The function may need to check many characters one by one, so longer strings usually take more time.

Interview Connect

Understanding how string search time grows helps you explain efficiency clearly and shows you know how basic functions behave with bigger data.

Self-Check

"What if we searched for multiple different substrings one after another? How would the time complexity change?"

Practice

1. What does the PHP function strpos do?

easy

A. Converts a string to uppercase

B. Extracts a substring starting from a specific character

C. Finds the position of a substring inside a string

D. Replaces a substring with another string

Solution

1. Step 1: Understand the purpose of strpos

   The strpos function searches for the first occurrence of a substring inside another string and returns its position.

2. Step 2: Compare with other options

   Options A, B, and C describe different string functions like strtoupper, strstr, and str_replace, which are not what strpos does.

3. Final Answer:

   Finds the position of a substring inside a string -> Option C

4. Quick Check:

   strpos = position finder [OK]

Hint: strpos returns position index of substring [OK]

Common Mistakes:

• Confusing strpos with strstr
• Thinking strpos extracts substring
• Assuming strpos replaces text

2. Which of the following is the correct syntax to find the position of 'cat' in the string $text = 'concatenate' using strpos?

easy

A. strpos('concatenate', 'cat')

B. strpos($text)

C. strpos('cat', $text)

D. strpos($text, 'cat')

Solution

1. Step 1: Identify correct parameter order for strpos

   The first parameter is the full string, the second is the substring to find. So strpos($text, 'cat') is correct.

2. Step 2: Check other options for errors

   strpos('concatenate', 'cat') uses a string literal instead of the variable. strpos('cat', $text) reverses parameters. strpos($text) misses the second parameter.

3. Final Answer:

   strpos($text, 'cat') -> Option D

4. Quick Check:

   strpos(string, substring) [OK]

Hint: First argument is full string, second is substring [OK]

Common Mistakes:

• Swapping the order of parameters
• Omitting the substring argument
• Passing substring as first argument

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

$text = 'hello world';
$pos = strpos($text, 'world');
echo $pos;

medium

A. 6

B. 5

C. 0

D. false

Solution

1. Step 1: Find the position of 'world' in 'hello world'

   The string 'hello world' has 'world' starting at index 6 (counting from 0).

2. Step 2: Understand what strpos returns

   strpos returns the starting position of the substring, so it returns 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Position of 'world' in 'hello world' = 6 [OK]

Hint: Count characters from zero to substring start [OK]

Common Mistakes:

• Counting from 1 instead of 0
• Confusing position with length
• Expecting boolean true instead of position

4. The following code is intended to check if the word 'apple' exists in $fruit. What is the error?

$fruit = 'pineapple';
if (strpos($fruit, 'apple')) {
  echo 'Found';
} else {
  echo 'Not found';
}

medium

A. strpos returns false if found, so condition is wrong

B. strpos returns 0 for 'apple' position, which is treated as false

C. Missing third parameter in strpos

D. Syntax error in if statement

Solution

1. Step 1: Understand strpos return values

   strpos returns 0 if the substring is found at the start (index 0). In PHP, 0 is treated as false in conditions.

2. Step 2: Analyze the if condition behavior

   The condition if (strpos(...)) fails when strpos returns 0, so it wrongly goes to else.

3. Final Answer:

   strpos returns 0 for 'apple' position, which is treated as false -> Option B

4. Quick Check:

   Check strpos !== false to avoid 0 as false [OK]

Hint: Check strpos !== false, not just if() [OK]

Common Mistakes:

• Using if(strpos()) without strict false check
• Assuming strpos returns boolean true/false only
• Ignoring 0 as valid position

5. Given the string $sentence = 'The quick brown fox jumps', which code snippet correctly extracts the substring starting from the word 'brown' using strstr?

hard

A. echo strstr($sentence, 'brown');

B. echo strstr($sentence, 'brown', true);

C. echo strpos($sentence, 'brown');

D. echo substr($sentence, strpos($sentence, 'brown'));

Solution

1. Step 1: Understand strstr behavior

   strstr returns the part of the string starting from the first occurrence of the substring, including it.

2. Step 2: Analyze options

   echo strstr($sentence, 'brown'); correctly uses strstr to get substring from 'brown'. echo strstr($sentence, 'brown', true); returns part before 'brown'. echo strpos($sentence, 'brown'); returns position, not substring. echo substr($sentence, strpos($sentence, 'brown')); uses substr with strpos, which also works but is not strstr.

3. Final Answer:

   echo strstr($sentence, 'brown'); -> Option A

4. Quick Check:

   strstr returns substring from needle [OK]

Hint: strstr returns substring from needle, true returns before [OK]

Common Mistakes:

• Using third parameter true to get substring after needle
• Confusing strpos with strstr
• Expecting strpos to return substring