Pattern Search - Naïve Algorithm

Pattern Searching algorithm is string matching algorithm which is used to find a pattern or a substring in another string.

1) Naïve Algorithm:

• Slide the pattern over the string and check for the match.
• Once you find the match, start iterating through the pattern to check for the subsequent matches.
• Length of pattern has to be less or equal to length of string, if pattern's length is greater than length of string return pattern not found.

def naïve_algorithm(string, pattern):
    n = len(string)
    m = len(pattern)
    if m > n: 
        print("Pattern not found")
        return
    for i in range(n - m + 1):
        j = 0
        while j < m:
            if string[i + j] != pattern[j]:
                break
            j += 1
        if j == map:
            print("Pattern found at index: ", i)

string = "hello"
pattern = "ll"
naïve_algorithm(string, pattern)

Time Complexity:

Complexity	value
Best	O(n)
Worst	O(m * n)

• Where m is the length of pattern and n is the length of string.

  Best Case - O(n):

  Happens when the string doesn't have the pattern.

  Worst Case - O(m * n):

  Happens when:

• All characters in both string and pattern are the same.

• All characters in both string and pattern are the same except for the last character.