Course contentsShow
← Computer Science
Lesson 831 of 2,87219. Searching and SelectionFree lesson

String Search Problem and Naive Approach

Define the string search problem, introduce the naive O(nm) brute-force algorithm, and analyze its performance characteristics.

String Search Problem and Naive Approach

What You'll Learn

You'll learn what the string search problem is and understand the simplest brute-force solution that checks every possible position.


The String Search Problem

The string search problem (also called pattern matching) asks: given a text string of length n and a pattern string of length m, find all occurrences of the pattern within the text.

Example: In the text "HELLO WORLD", find the pattern "LO". The pattern occurs at position 3.

This problem appears everywhere: text editors (Ctrl+F), DNA sequence analysis, plagiarism detection, and search engines.


The Naive Approach

The simplest solution is to check every possible starting position in the text:

  1. Start at position 0 in the text
  2. Compare the pattern character-by-character with the text at this position
  3. If all characters match, record this position
  4. Move to the next position and repeat

Analogy: Imagine sliding a stencil (the pattern) over a long piece of paper (the text), checking at each position whether the stencil matches what's underneath.


Performance Analysis

Time Complexity: O(n × m)

  • In the worst case, you check all n positions
  • At each position, you might compare up to m characters
  • Example worst case: text = "AAAAAAA", pattern = "AAAB" — you compare almost all pattern characters before failing at each position

Space Complexity: O(1)

  • Only need a few variables to track positions

The naive approach is simple to implement but inefficient for large texts or patterns. It doesn't learn from previous comparisons or skip positions intelligently.


Key Takeaway: The string search problem finds patterns in text; the naive O(nm) approach checks every position by brute-force character comparison, but wastes work by not remembering previous mismatches.