Naïve String Matching Algorithm in Python: Examples, Featured & Pros & Cons
By Rohit Sharma
Updated on Apr 01, 2025 | 6 min read | 11.0k views
Share:
For working professionals
For fresh graduates
More
By Rohit Sharma
Updated on Apr 01, 2025 | 6 min read | 11.0k views
Share:
Table of Contents
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.
To Explore all our courses, visit our machine learning courses
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.
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].
Note that the length of the input text or string will always be greater than or equal to that of the pattern.
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
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!
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).
There are two worst cases in the naïve string searching approach.
T [] = “EEEEEEEEEEEEEEEE”;
P [] = “EEE”;
T [] = “EEEEEEEEEEED”;
P [] = “EEEED”;
In such cases, the number of comparisons in O(m*(n-m+1)).
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.
Also read: Data Structure & Algorithm in Python
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.
Check out the trending Python Tutorial concepts in 2024
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.
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
Top Resources