t = 'haystack needle haystack' # "text" - thing we search in
p = 'needle' # "pattern" - thing we search for
def naive(p, t):
assert len(p) <= len(t) # assume text at least as long as pattern
occurrences = []
# For each alignment of p to t
for i in xrange(0, len(t)-len(p)+1):
match = True # assume the pattern matches until proven wrong
# For each position of p
for j in xrange(0, len(p)):
if t[i+j] != p[j]:
match = False # at least 1 char mismatches, so no match
break
if match:
occurrences.append(i)
return occurrences
naive(p, t)
[9]
t[9:9+len(p)] # let's confirm it really occurs
'needle'
naive('needle', 'needleneedleneedle')
[0, 6, 12]