What is Anagram Substring Search? Explain using program in Python

In this post, we are going to study about another string searching technique. String searching algorithms are important when we have to find relevant keywords and encrypted codes in text. Learn Anagram Substring Search in Python with examples.

What is Anagram Substring Search?

Anagrams are strings that are formed by the rearrangement of the same alphabets. eg, cat, act, tac are anagrams of each other. Another example could be AAB, ABA, BAA are anagram strings. In this article, the goal is to find all the anagrams present for a given substring from another string.
For eg, let the string  a=”BACDGABCDA”. We have to find all the anagrams of the substring b=”ABCD” from string a. How we will do that?

  • Iterate through the entire string and extract substrings of length ‘b’,( here 4) at every index position.
  • Check if the extracted substring is an anagram of the substring ‘a’.

Let us see the code for it. In the python code below, we have divided our program into two functions:

  1. def isanagram(s1,s2):– This function checks whether the two strings are anagrams or not. This function takes two arguments, s1 and s2. ‘s1’ is the extracted substring that has been passed after iteration and ‘s2’ is the given substring that has to be matched. This is done by the in-built function sorted(). sorted() returns the sorted list of the characters of the string. The sorted lists of the anagrams will always be the same. Now after checking, the function isanagram() returns True if the strings are anagrams else it returns False.
  2. def search(txt,wrd):- This function iterates through the entire string and extracts substrings at every index position. After calling the isanagram() function it prints the index position if True is returned otherwise it prints the message “not found”. This is Naive String searching technique used in this function.

Below is the code:-

def isanagram(s1,s2): 
    #function to check if the strins are anagram or not
    if sorted(s1)==sorted(s2):
        return True
    else:
        return False
    
def search(txt,wrd):
    #function to iterate through the string
    t=0
    lt=len(txt)
    lw=len(wrd)
    for i in range(lt-lw+1):
         if isanagram(txt[i:i+lw],wrd):
                t=1
                print("found at position",i)
    if t==0:
        print("Anagram not found")

Let’s see the result for various inputs:-

String- “The cat acts tactfully”;  Substring:- “cat”

search("The cat acts tactfully","cat")

Output-

Leave a Reply

Your email address will not be published. Required fields are marked *