Naive Text Search Algorithm in Python

In this tutorial, we will look at identifying patterns in text. There will be a substring in addition to the main content. The purpose is to determine how many times the substring appears in the text and at what locations.

This pattern-finding approach is useful when there is a large text and we need to locate the occurrences of specific keywords or terms.

In this section, we will discuss the most basic ‘Naive String Matching Algorithm in Python’ and how to improve it through better and shorter code.

Introduction to Naive Algorithm

As the phrase implies, Naive Algorithms are algorithms that are very basic and easy to implement. These algorithms use the most basic and apparent strategies to complete tasks like a kid would.

These approaches are a good place for beginners to start before moving on to more efficient and intricate algorithms. One of them is a basic string searching algorithm. Among the string matching/pattern-finding algorithms, it is the most basic.

The process begins with letter-by-letter matching the string. It searches for the first character in both the main text and the substring. If it matches, it continues to the next character in both strings.

If the characters do not match anywhere in the loop, the loop is broken, and the loop is restarted from the next character in the main text string.

Implementing Naive String Searching From

def naive(txt,wrd):
    lt=len(txt)#length of the string
    lw=len(wrd)/3length of the substring(pattern)
    for i in range(lt-lw+1):
        j=0
        while(j<lw):
            if txt[i+j]==wrd[j]:
                j+=1
            else:
                break
        else:
            print('found at position',i)

The method ‘naive’ in the code above takes two arguments: txt (the primary string from which the pattern is to be sought) and ward (the pattern to be searched).

Since at least the length of the substring should be left to be matched towards the end, a loop is taken from 0 to (length of string-length of substring+1). The ‘for’ loop extracts each character from the string (text[I]).

Then there’s an inner while loop that compares that character to the next character in the substring until the entire substring is matched. If it is not discovered, the loop is broken, and the following iteration, as in the next character, is removed from the process.

When the complete substring is discovered, the while condition is broken, the otherwise section is run, and the location is displayed. One else is within the loop and is only run when the if the condition is false, whereas the other is executed when the while loop condition is false.

Let’s look at the output for the following input:

naive("AABAACAADAABAABA","AABA")

The output comes out to be the following:

found at position 0
found at position 9
found at position 12

Conclusion

Congratulations! You just learned how to implement the Naive String Searching Algorithm. Hope you enjoyed it! 😇

Liked the tutorial? In any case, I would recommend you to have a look at the tutorials mentioned below:

Thank you for taking your time out! Hope you learned something new!! 😄