Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconArtificial Intelligencebreadcumb forward arrow iconNaïve String Matching Algorithm in Python: Examples, Featured & Pros & Cons

Naïve String Matching Algorithm in Python: Examples, Featured & Pros & Cons

Last updated:
14th May, 2020
Views
Read Time
6 Mins
share image icon
In this article
Chevron in toc
View All
Naïve String Matching Algorithm in Python: Examples, Featured & Pros & Cons

When there is a need to find an input pattern in a string of characters, coders and programmers use the string matching algorithm. Usually, in case of a short string, python programmers prefer to use the naïve approach in which, the program checks each position in the input string for the query pattern. In case it matches, it given an output with the position number.

Best Machine Learning and AI Courses Online

One of the biggest reasons why naïve string matching algorithm is used is because it is fast and yields quite accurate results. Moreover, it does not require pre-processing. In any case, we will be discussing these advantages at a later stage in this post. Let’s first understand the algorithm for pattern search using the naïve approach.

Naïve Pattern Search Algorithm

In the naïve string pattern search, the program tests the position of the input pattern P [1……i] in a string of characters T [1…..m]. 

Ads of upGrad blog

Note that the length of the input text or string will always be greater than or equal to that of the pattern.

In-demand Machine Learning Skills

Here is the naïve pattern search algorithm for different programming languages.

Begin

   pat = pattern Size

   str = string size

   for i = 0 to (str – pat), do

      for j = 0 to pat, do

         if text[i+j] ≠ pattern[j], then

            break the loop

      done

      if j == pat, then

         display the position of i as pattern found

   done

End

This algorithm is quite an important one in computer science, as it helps give search results as an ouput.

Read : Types of AI Algorithms You Should Know

Examples of Naïve String Matching on Python

Here is an example where the naïve pattern search approach is used in a code of python.

# Python program for Naïve String Matching

# Searching algorithm 

def search(P, T): 

    X = len(P) 

    Y = len(T) 

    # A loop to shift P[] one by one */ 

    for i in range(X Y + 1): 

        j = 0  

        # For current index i, check  

        # for pattern match */ 

        for j in range(0, X): 

            if (txt[i + j] != P[j]): 

                break

        if (j == X 1):  

            print(“Pattern found at position “, i) 

# Driver Code 

if __name__ == ‘__main__’: 

    T = “UPGRADEDUBUPGRAABUPGRADEDU”

    P = “UPGRAD”

    search(P, T) 

Output:

Pattern found at position 0

Pattern found at position 17

Explanation: The first position is the 0th position. Since the pattern “UPGRAD” was first spotted here, the output showed that the pattern is found at position 0.

Similarly, the next pattern was found at the position 17.

FYI: Free Deep Learning Course!

Best Case of Naïve Pattern Search

There in only one best case for naïve pattern search algorithm, unlike the two worst cases.

The best case occurs when the first character in the pattern text is nowhere in the input string.

Example:

T [] = “UPGRADEDUHIJKLUPGRA”;

P [] = “TUPGRA”;

And therefore, the number of matching patterns case is O(n).

Worst Case of Naïve Pattern Search

There are two worst cases in the naïve string searching approach.

  1. When all the characters in the pattern are the same as those in the input string.

T [] = “EEEEEEEEEEEEEEEE”;

P [] = “EEE”;

  1. When only the last character in the pattern differs from the input string.

T [] = “EEEEEEEEEEED”;

P [] = “EEEED”;

In such cases, the number of comparisons in O(m*(n-m+1)).

Features of Naïve String Matching Algorithm

String matching algorithm is meant for finding all the occurrences of a given pattern in a text.

Here are the top features of the algorithm.

  1. It is the simplest method among all to look for patterns in an input text. It checks all the characters one by one in the given string of characters.
  2. It finds the exact string matches – be it more or more exact occurrences of the pattern.
  3. It is more used when there is small text. Moreover, it does not require any pre-processing phases.
  4. This search method does not occupy extra space to work and look for the patterns in the string.

Also read: Data Structure & Algorithm in Python

Advantages of Naïve Pattern Search

  1. There are no pre-processing phases required in the naïve search approach, as its running time is equal to the matching time.
  2. There is no extra operating space needed.
  3. The comparisons of the patterns with the strings can be done in any order.

Disadvantages of Naïve String Matching

There is only one disadvantage of the naïve string matching approach, which is that it is inefficient. This is because when it has found a position, it does not use it again to find the other position. It goes back to the starting point and looks for the pattern over again. And so, it does not use the information from the previous shift again.

Popular AI and ML Blogs & Free Courses

Check out the trending Python Tutorial concepts in 2024

Conclusion

Ads of upGrad blog

The naïve string matching algorithm is the most preferred approach to finding the positions of said patterns in a given text for various reasons like no pre-processing requirement, no extra space for operation, etc. However, it cannot be used for rather larger texts because of its inefficiency to perform large operations faster.

We hope that this post gave you a substantially good idea about the naïve pattern search approach in python. To learn about the uses of this approach and get a broader understanding of the topic, get in touch with the experts at upGrad. We have specially designed courses for individuals looking to expand their skillset. Reach out to us today!

If you’re interested to learn more about AI, machine learning, check out IIIT-B & upGrad’s PG Diploma in Machine Learning & AI which is designed for working professionals and offers 450+ hours of rigorous training, 30+ case studies & assignments, IIIT-B Alumni status, 5+ practical hands-on capstone projects & job assistance with top firms.

Profile

Rohit Sharma

Blog Author
Rohit Sharma is the Program Director for the UpGrad-IIIT Bangalore, PG Diploma Data Analytics Program.
Get Free Consultation

Select Coursecaret down icon
Selectcaret down icon
By clicking 'Submit' you Agree to  
UpGrad's Terms & Conditions

Our Popular Machine Learning Course

Frequently Asked Questions (FAQs)

1What is a naïve string-matching algorithm?

A naive string-matching algorithm is one that simply compares the two strings character by character. This naive algorithm is used by many early computer programs that implemented simple file searching functions. In other words, the strings are compared character for character and the algorithm stops once a mismatch is found. This is an inappropriate way to do string matching as it is slow and wasteful of memory. This is very inefficient since the number of strings in a text is humongous but the search query is only a few characters.

2What are the limitations of naïve algorithms for string matching?

Unsatisfiability of 8-queens and related problems as NP-complete show that naïve string-matching algorithms have limitations. Naïve string-matching algorithm will not give you the solution. In case of string-matching it requires exponential time. So, if you have n strings to be matched, it will take 2n time to complete. To get around this problem an algorithm has been developed which has made the string-matching problem feasible. This algorithm, which is an exponential time algorithm, is called Aho-Corasick algorithm. This algorithm works on the principle of dynamic programming.

3How can we optimize naive string-matching algorithms?

Optimization of naïve string-matching algorithms is done in two ways:
1) String database search: This is the best solution for database search. It is fast, but requires a huge budget.
2) Tries: These are a great alternative to the database, because they can be made from memory, which keeps them low-budget. You can easily represent the string in a binary tree form. Then, you just go through the tree, and check for the result. If you find that you are at the end of the tree, you have found a good match. There is no need to go back to the beginning of the tree. This algorithm is fast, but it does not allow for long strings to be compared.

Explore Free Courses

Suggested Blogs

Artificial Intelligence course fees
5215
Artificial intelligence (AI) was one of the most used words in 2023, which emphasizes how important and widespread this technology has become. If you
Read More

by venkatesh Rajanala

29 Feb 2024

Artificial Intelligence in Banking 2024: Examples & Challenges
5718
Introduction Millennials and their changing preferences have led to a wide-scale disruption of daily processes in many industries and a simultaneous g
Read More

by Pavan Vadapalli

27 Feb 2024

Top 9 Python Libraries for Machine Learning in 2024
75264
Machine learning is the most algorithm-intense field in computer science. Gone are those days when people had to code all algorithms for machine learn
Read More

by upGrad

19 Feb 2024

Top 15 IoT Interview Questions & Answers 2024 – For Beginners & Experienced
64237
These days, the minute you indulge in any technology-oriented discussion, interview questions on cloud computing come up in some form or the other. Th
Read More

by Kechit Goyal

19 Feb 2024

Data Preprocessing in Machine Learning: 7 Easy Steps To Follow
151420
Summary: In this article, you will learn about data preprocessing in Machine Learning: 7 easy steps to follow. Acquire the dataset Import all the cr
Read More

by Kechit Goyal

18 Feb 2024

Artificial Intelligence Salary in India [For Beginners & Experienced] in 2024
908007
Artificial Intelligence (AI) has been one of the hottest buzzwords in the tech sphere for quite some time now. As Data Science is advancing, both AI a
Read More

by upGrad

18 Feb 2024

24 Exciting IoT Project Ideas & Topics For Beginners 2024 [Latest]
755258
Summary: In this article, you will learn the 24 Exciting IoT Project Ideas & Topics. Take a glimpse at the project ideas listed below. Smart Agr
Read More

by Kechit Goyal

18 Feb 2024

Natural Language Processing (NLP) Projects & Topics For Beginners [2023]
106862
What are Natural Language Processing Projects? NLP project ideas advanced encompass various applications and research areas that leverage computation
Read More

by Pavan Vadapalli

17 Feb 2024

45+ Interesting Machine Learning Project Ideas For Beginners [2024]
326845
Summary: In this Article, you will learn Stock Prices Predictor Sports Predictor Develop A Sentiment Analyzer Enhance Healthcare Prepare ML Algorith
Read More

by Jaideep Khare

16 Feb 2024

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon