Naive Pattern Matching
Try the pattern at every shift and compare character by character. Simple and fine for short patterns, but re-examines text it has already seen — O(n·m) worst case.
- Category
- Strings
- Time complexity
- O(n·m)
- Space complexity
- O(1)
Pseudocode
for each shift s compare pattern to text[s..] mismatch → shift by 1, restart full match → report s
Reference implementation
for s in range(n - m + 1):
if text[s:s+m] == pat:
return s
# re-compares old characters