substrings_search_naive_en.py

#Naive algorithm to search all the appearences of a substring inside string
def search_naive(needle, haystack): #Search for a needle (i.e. search request) inside a haystack (i.e. text where we search)
    n = len(haystack)
    k = len(needle)
    result = []
    for i in range(n-k+1): #this is actually just a sliding window approach
        are_equal = True
        for j in range(k):
            are_equal = (haystack[i+j] == needle[j])
            if not are_equal:
                break
        if are_equal:
            result.append(i) #if we find an appearance we just add a position to results
    return result

haystack = 'abbabcbabcbaabc' #consider this 'text' - haystack
needle = 'abc' #and this is a simple search request
search_naive(needle, haystack) #let's call for our naive search function
#Output is [3, 7, 12]