In [1]:

    

t = 'haystack needle haystack' # "text" - thing we search in
p = 'needle' # "pattern" - thing we search for


    

In [2]:

    

def naive(p, t):
    assert len(p) <= len(t)  # assume text at least as long as pattern
    occurrences = []
    for i in range(len(t)-len(p)+1):  # for each alignment of p to t
        match = True  # assume we match until proven wrong
        for j in range(len(p)):  # for each position of p
            if t[i+j] != p[j]:
                match = False  # at least 1 char mismatches
                break
        if match:
            occurrences.append(i)
    return occurrences


    

In [3]:

    

naive(p, t)


    

    
Out[3]:





[9]

In [4]:

    

t[9:9+len(p)]  # confirm it really occurs


    

    
Out[4]:





'needle'

In [5]:

    

naive('needle', 'needleneedleneedle')


    

    
Out[5]:





[0, 6, 12]