DEV Community

Cover image for Pattern Search - Naïve Algorithm
Hagar
Hagar

Posted on • Edited on

5 1

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:

string and pattern

  • Slide the pattern over the string and check for the match. Search 1
  • Once you find the match, start iterating through the pattern to check for the subsequent matches. Search 2
  • 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)

Enter fullscreen mode Exit fullscreen mode

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.

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay