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:
- Start at position 0 in the text
- Compare the pattern character-by-character with the text at this position
- If all characters match, record this position
- 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
npositions - At each position, you might compare up to
mcharacters - 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.