Naive Pattern Search
Naive pattern search finds all occurrences of a pattern in a text by checking every position.
30 COMPARISONS TOTAL
MATCH
A
0
A
1
B
2
A
3
A
4
C
5
A
6
A
7
D
8
A
9
A
10
B
11
A
12
A
13
B
14
A
15
Comparisons
1
Matches
0
Pattern, aligned at index 0
A
A
B
A
'A' at 0 matches pattern[0].
Next
'A' at 1 matches pattern[1].
Text
Pattern
Intuition
Slide the pattern over the text one by one and check for a match. If a match is found, record the index. If a mismatch occurs, shift the pattern by one position.
Concept
- Sliding Window: The pattern acts as a window of length M.
- Comparison: Compare character by character.
- Shift: Move window by 1 after every check.
How it Works
Algorithm:
- Loop
ifrom0toN - M. - For each
i, loopjfrom0toM - 1. - If
text[i+j] != pattern[j], break inner loop. - If inner loop completes (j == M), pattern found at
i.
Step-by-Step Breakdown
Watch the visualization:
- The pattern row sits under the part of the text it is being compared against, and slides one position at a time.
- Solid blue: The character pair being compared; it turns red on a mismatch.
- Pale blue with a blue outline: Characters already matched at this alignment.
- Green: Text characters of an occurrence that was found.
When to Use
- Small texts or patterns.
- When simplicity is preferred over performance.
When NOT to Use
- Large texts (O(N*M) is too slow). Use KMP or Rabin-Karp instead.
How to Identify
"Find occurrence of pattern", "Substring search".
Applying for software engineering roles? Free, no sign-up: