String matching basics in Data Structures Theory - Time & Space Complexity

Time Complexity: String matching basics

O(n x m)

Understanding Time Complexity

When we search for a smaller word or pattern inside a bigger text, we want to know how long it takes as the text grows.

We ask: How does the time to find the pattern change when the text gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function simpleMatch(text, pattern) {
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j = 0;
    while (j < pattern.length && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === pattern.length) {
      return i; // pattern found at index i
    }
  }
  return -1; // pattern not found
}
    

This code checks each position in the text to see if the pattern starts there by comparing characters one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking characters of the pattern against the text at each possible start position.
• How many times: The outer loop runs roughly (text length - pattern length + 1) times, and the inner loop runs up to the pattern length times for each outer loop.

How Execution Grows With Input

As the text gets longer, the number of places to check grows, and for each place, we may compare many characters.

Input Size (text length n)	Approx. Operations
10	Up to 10 x pattern length comparisons
100	Up to 100 x pattern length comparisons
1000	Up to 1000 x pattern length comparisons

Pattern observation: The work grows roughly in a straight line with the text length multiplied by the pattern length.

Final Time Complexity

Time Complexity: O(n × m)

This means the time to find the pattern grows proportionally to the text length times the pattern length.

Common Mistake

[X] Wrong: "The search always takes time proportional only to the text length."

[OK] Correct: Because for each position in the text, we may need to check many characters of the pattern, so the pattern length also affects the time.

Interview Connect

Understanding how searching text works helps you explain and improve basic algorithms, a useful skill in many coding challenges and real projects.

Self-Check

"What if we used a more advanced algorithm that skips some checks? How would the time complexity change?"