String searching (contains, strfind) in MATLAB - Time & Space Complexity

Time Complexity: String searching (contains, strfind)

O(n*m)

Understanding Time Complexity

We want to understand how the time it takes to search for a smaller string inside a bigger string changes as the strings get longer.

How does the search time grow when the input strings grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = 'hello world, welcome to matlab';
pattern = 'come';
index = strfind(text, pattern);
found = contains(text, pattern);

This code looks for the smaller string pattern inside the bigger string text using two functions: strfind and contains.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each position in the big string to see if the smaller string starts there.
• How many times: For each character in the big string, it compares up to the length of the smaller string.

How Execution Grows With Input

As the big string gets longer, the number of checks grows roughly by the length of the big string times the length of the smaller string.

Input Size (n)	Approx. Operations
10	About 10 times length of pattern
100	About 100 times length of pattern
1000	About 1000 times length of pattern

Pattern observation: The work grows roughly in a straight line with the big string size, multiplied by the smaller string size.

Final Time Complexity

Time Complexity: O(n*m)

This means the time to search grows proportionally to the length of the big string times the length of the smaller string.

Common Mistake

[X] Wrong: "Searching for a string inside another always takes the same time no matter how long the strings are."

[OK] Correct: The search checks many positions and compares characters, so longer strings mean more work and more time.

Interview Connect

Understanding how string search time grows helps you explain and reason about code efficiency clearly, a useful skill in many programming tasks.

Self-Check

"What if the smaller string is always just one character? How would the time complexity change?"

Practice

1. Which MATLAB function returns a logical true or false indicating if a substring exists within a string?

easy

A. contains

B. strfind

C. findstr

D. substring

Solution

1. Step 1: Understand the purpose of contains

   contains returns true or false if a substring is found inside a string.

2. Step 2: Compare with strfind

   strfind returns positions, not logical true/false.

3. Final Answer:

   contains -> Option A

4. Quick Check:

   Logical check for substring = contains [OK]

Hint: Use contains for true/false substring check [OK]

Common Mistakes:

• Confusing strfind with contains
• Thinking strfind returns true/false
• Using findstr which is outdated

2. Which of the following is the correct syntax to find the starting indices of substring 'cat' in string str = 'concatenate' using strfind?

easy

A. contains(str, 'cat')

B. strfind('cat', str)

C. strfind(str, 'cat')

D. strfind(str, cat)

Solution

1. Step 1: Recall strfind syntax

   The first argument is the main string, second is the substring to find.

2. Step 2: Check each option

   strfind(str, 'cat') correctly uses strfind(str, 'cat'). strfind('cat', str) reverses arguments. contains(str, 'cat') uses contains, not strfind. strfind(str, cat) misses quotes around 'cat'.

3. Final Answer:

   strfind(str, 'cat') -> Option C

4. Quick Check:

   strfind(mainString, substring) = strfind(str, 'cat') [OK]

Hint: First argument main string, second substring in strfind [OK]

Common Mistakes:

• Swapping arguments in strfind
• Forgetting quotes around substring
• Using contains instead of strfind for indices

3. What is the output of the following MATLAB code?

str = 'abracadabra';
pos = strfind(str, 'ra');
disp(pos);

medium

A. [3 10]

B. [2 9]

C. [4 11]

D. []

Solution

1. Step 1: Identify substring positions in 'abracadabra'

   Look for 'ra' in the string: 'abracadabra'. The substring 'ra' starts at index 3 and 10.

2. Step 2: Confirm output of strfind

   strfind returns starting indices of matches, so output is [3 10].

3. Final Answer:

   [3 10] -> Option A

4. Quick Check:

   Positions of 'ra' = [3 10] [OK]

Hint: Count string indices carefully for strfind output [OK]

Common Mistakes:

• Counting indices starting at 0 instead of 1
• Confusing substring length with position
• Expecting logical output instead of indices

4. Identify the error in this MATLAB code snippet:

str = 'hello world';
pos = strfind('world', str);
disp(pos);

medium

A. disp cannot display arrays

B. Arguments of strfind are reversed

C. strfind cannot search for 'world'

D. Missing semicolon after strfind

Solution

1. Step 1: Check strfind argument order

   strfind expects the main string first, then the substring. Here, arguments are reversed.

2. Step 2: Understand impact of reversed arguments

   Searching 'world' inside 'hello world' is correct, but reversed arguments cause wrong or empty output.

3. Final Answer:

   Arguments of strfind are reversed -> Option B

4. Quick Check:

   strfind(mainString, substring) correct order [OK]

Hint: Main string first, substring second in strfind [OK]

Common Mistakes:

• Swapping arguments in strfind
• Assuming disp can't show arrays
• Thinking semicolon is mandatory for correctness

5. You want to find all positions of the substring 'ana' in str = 'banana bandana' and check if it exists. Which code correctly does this?

hard

A. positions = strfind('ana', str); exists = contains('ana', str);

B. positions = contains(str, 'ana'); exists = strfind(str, 'ana');

C. positions = find(str, 'ana'); exists = contains(str, 'ana');

D. positions = strfind(str, 'ana'); exists = contains(str, 'ana');

Solution

1. Step 1: Use strfind to get positions

   strfind(str, 'ana') returns all starting indices of 'ana' in the string.

2. Step 2: Use contains to check existence

   contains(str, 'ana') returns true if 'ana' is found anywhere in str.

3. Step 3: Verify options

   positions = strfind(str, 'ana'); exists = contains(str, 'ana'); correctly uses both functions. positions = contains(str, 'ana'); exists = strfind(str, 'ana'); swaps roles. positions = strfind('ana', str); exists = contains('ana', str); reverses arguments. positions = find(str, 'ana'); exists = contains(str, 'ana'); uses invalid function find for strings.

4. Final Answer:

   positions = strfind(str, 'ana'); exists = contains(str, 'ana'); -> Option D

5. Quick Check:

   Positions with strfind, existence with contains [OK]

Hint: Use strfind for positions, contains for true/false [OK]

Common Mistakes:

• Swapping arguments in strfind or contains
• Using find instead of strfind
• Confusing output types of contains and strfind