StringsString Algorithms

Naive String Matching

Try every alignment of the pattern against the text and compare character by character.

Learn Naive String Matching →
a
a
0
b
1
x
2
a
3
b
4
c
5
a
6
b
7
c
8
a
9
b
10
y
11
pattern
a
0
b
1
c
2
a
3
b
4
y
5
1/35Try every alignment s of the pattern (length 6) against the text (length 12); there are 7 of them.
Characters being comparedMatchMismatch at this alignment
PseudocodeLearn Naive String Matching →
1for s in 0 .. n-m:
2  j = 0
3  while j < m and text[s+j] == pattern[j]:
4    j += 1
5  if j == m: report match at s
6return matches
Variables
n12
m6
Complexity
best O(n)
avg O(n + m)
worst O(n · m)
space O(1)
Speed