Anagram Substring Search (Or Search for all permutations) | Set 2

0 0 7 minutes read

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] and its permutations (or anagrams) in txt[]. You may assume that n > m.

Examples:

Input: txt[] = “BACDGABCDA” pat[] = “ABCD”
Output: Found at Index 0
Found at Index 5
Found at Index 6

Input: txt[] = “AAABABAA” pat[] = “AABA”
Output: Found at Index 0
Found at Index 1
Found at Index 4

Approach: The current approach is based on sliding window and hashtable.

Create a hashtable to store a hash of all characters in the pattern
Create a hashtable to store a hash of all characters in text for window m
Traverse the string text in window m and compare the hashtables.
If found the same, push the index of substring as one of the answers.

Below is the implementation of the above approach:

C++

// C++ program to search all anagrams
// of a pattern in a text
 
#include <bits/stdc++.h>
#define MAX 256
using namespace std;
 
// Function to find all anagrams using hashtable
vector<int> findAnagrams(string s, string p)
{
    int n = s.length(), m = p.length();
 
    // Vector to store all indices of substrings
    // that are anagram of string p
 
    vector<int> ans;
 
    // Handling edge cases
    if (n < m || m == 0)
        return ans;
 
    // Hashtables for both strings
    vector<int> ms(26, 0), mp(26, 0);
 
    // Initialise the hashtable for string p
    for (char c : p) {
        mp++;
    }
 
    int i = 0;
    bool flag = true;
 
    // Initialise the hashtable
    // for string s for window m
    for (i = 0; i < m; i++) {
        ms[s[i] - 'A']++;
    }
 
    // Check if current hashtables are same
    // for current window m
 
    for (int j = 0; j < 26; j++)
        if (mp[j] != ms[j])
            flag = false;
 
    // if same, push the index of
    // Starting substring into window m
 
    if (flag)
        ans.push_back(0);
 
    // Traverse string s with window m
    for (i = m; i < n; i++) {
        ms[s[i - m] - 'A']--;
        ms[s[i] - 'A']++;
 
        // Check if current hashtables are same
        // for current window m
        if (mp[s[i] - 'A'] == ms[s[i] - 'A']
            && mp[s[i - m] - 'A'] == ms[s[i - m] - 'A']) {
            flag = true;
            for (int j = 0; j < 26; j++)
                if (mp[j] != ms[j])
                    flag = false;
        }
        else
            flag = false;
 
        // if same, push the index
        // of starting substring
        // into answer
        if (flag)
            ans.push_back(i - m + 1);
    }
 
    // Return the final vector of indices
    return ans;
}
 
// Driver program
int main()
{
    char txt[] = "BACDGABCDA";
    char pat[] = "ABCD";
    vector<int> indices = findAnagrams(txt, pat);
    cout << "[ ";
    for (auto i : indices)
        cout << i << " ";
    cout << "]";
    return 0;
}

Java

// Java program to search all anagrams
// of a pattern in a text
import java.util.*;
 
class GFG
{
  static final int MAX = 256;
 
  // Function to find all anagrams using hashtable
  static Vector<Integer> findAnagrams(String s, String p)
  {
    int n = s.length(), m = p.length();
 
    // Vector to store all indices of subStrings
    // that are anagram of String p
 
    Vector<Integer> ans = new Vector<Integer>();
 
    // Handling edge cases
    if (n < m || m == 0)
      return ans;
 
    // Hashtables for both Strings
    int [] ms = new int[26];
    int [] mp = new int[26];
 
    // Initialise the hashtable for String p
    for (char c : p.toCharArray()) {
      mp++;
    }
 
    int i = 0;
    boolean flag = true;
 
    // Initialise the hashtable
    // for String s for window m
    for (i = 0; i < m; i++) {
      ms[s.charAt(i) - 'A']++;
    }
 
    // Check if current hashtables are same
    // for current window m
 
    for (int j = 0; j < 26; j++)
      if (mp[j] != ms[j])
        flag = false;
 
    // if same, push the index of
    // Starting subString into window m
 
    if (flag)
      ans.add(0);
 
    // Traverse String s with window m
    for (i = m; i < n; i++) {
      ms[s.charAt(i-m) - 'A']--;
      ms[s.charAt(i) - 'A']++;
 
      // Check if current hashtables are same
      // for current window m
      if (mp[s.charAt(i) - 'A'] == ms[s.charAt(i) - 'A']
          && mp[s.charAt(i-m) - 'A'] == ms[s.charAt(i-m) - 'A']) {
        flag = true;
        for (int j = 0; j < 26; j++)
          if (mp[j] != ms[j])
            flag = false;
      }
      else
        flag = false;
 
      // if same, push the index
      // of starting subString
      // into answer
      if (flag)
        ans.add(i - m + 1);
    }
 
    // Return the final vector of indices
    return ans;
  }
 
  // Driver program
  public static void main(String[] args)
  {
    String txt = "BACDGABCDA";
    String pat = "ABCD";
    Vector<Integer> indices = findAnagrams(txt, pat);
    System.out.print("[ ");
    for (int i : indices)
      System.out.print(i+ " ");
    System.out.print("]");
  }
}
 
// This code is contributed by shikhasingrajput

Python3

# python3 program to search all anagrams
# of a pattern in a text
MAX = 256
 
# Function to find all anagrams using hashtable
def findAnagrams(s, p):
 
    n, m = len(s), len(p)
 
    # Vector to store all indices of substrings
    # that are anagram of string p
 
    ans = []
 
    # Handling edge cases
    if (n < m or m == 0):
        return ans
 
    # Hashtables for both strings
    ms, mp = [0 for _ in range(26)], [0 for _ in range(26)]
 
    # Initialise the hashtable for string p
    for c in p:
        mp[ord(c) - ord('A')] += 1
 
    i = 0
    flag = True
 
    # Initialise the hashtable
    # for string s for window m
    for i in range(0, m):
        ms[ord(s[i]) - ord('A')] += 1
 
    # Check if current hashtables are same
    # for current window m
 
    for j in range(0, 26):
        if (mp[j] != ms[j]):
            flag = False
 
    # if same, push the index of
    # Starting substring into window m
 
    if (flag):
        ans.append(0)
 
    # Traverse string s with window m
    for i in range(m, n):
        ms[ord(s[i - m]) - ord('A')] -= 1
        ms[ord(s[i]) - ord('A')] += 1
 
        # Check if current hashtables are same
        # for current window m
        if (mp[ord(s[i]) - ord('A')] == ms[ord(s[i]) - ord('A')]
                and mp[ord(s[i - m]) - ord('A')] == ms[ord(s[i - m]) - ord('A')]):
            flag = True
            for j in range(0, 26):
                if (mp[j] != ms[j]):
                    flag = False
 
        else:
            flag = False
 
        # if same, push the index
        # of starting substring
        # into answer
        if (flag):
            ans.append(i - m + 1)
 
    # Return the final vector of indices
    return ans
 
# Driver program
if __name__ == "__main__":
 
    txt = "BACDGABCDA"
    pat = "ABCD"
    indices = findAnagrams(txt, pat)
    print("[ ", end="")
    for i in indices:
        print(i, end=" ")
    print("]")
 
# This code is contributed by rakeshsahni

C#

// C# program to search all anagrams
// of a pattern in a text
using System;
using System.Collections;
 
class GFG {
 
    static int MAX = 256;
 
    // Function to find all anagrams using hashtable
    static ArrayList findAnagrams(string s, string p)
    {
        int n = s.Length, m = p.Length;
 
        // Vector to store all indices of subStrings
        // that are anagram of String p
 
        ArrayList ans = new ArrayList();
 
        // Handling edge cases
        if (n < m || m == 0)
            return ans;
 
        // Hashtables for both Strings
        int[] ms = new int[26];
        int[] mp = new int[26];
 
        // Initialise the hashtable for String p
        foreach(char c in p.ToCharArray())
        {
            mp++;
        }
 
        int i = 0;
        bool flag = true;
 
        // Initialise the hashtable
        // for String s for window m
        for (i = 0; i < m; i++) {
            ms[s[i] - 'A']++;
        }
 
        // Check if current hashtables are same
        // for current window m
 
        for (int j = 0; j < 26; j++)
            if (mp[j] != ms[j])
                flag = false;
 
        // if same, push the index of
        // Starting subString into window m
 
        if (flag)
            ans.Add(0);
 
        // Traverse String s with window m
        for (i = m; i < n; i++) {
            ms[s[i - m] - 'A']--;
            ms[s[i] - 'A']++;
 
            // Check if current hashtables are same
            // for current window m
            if (mp[s[i] - 'A'] == ms[s[i] - 'A']
                && mp[s[i - m] - 'A']
                       == ms[s[i - m] - 'A']) {
                flag = true;
                for (int j = 0; j < 26; j++)
                    if (mp[j] != ms[j])
                        flag = false;
            }
            else
                flag = false;
 
            // if same, push the index
            // of starting subString
            // into answer
            if (flag)
                ans.Add(i - m + 1);
        }
 
        // Return the final vector of indices
        return ans;
    }
 
    // Driver program
    public static void Main()
    {
        string txt = "BACDGABCDA";
        string pat = "ABCD";
        ArrayList indices = findAnagrams(txt, pat);
        Console.Write("[ ");
        foreach(int i in indices) Console.Write(i + " ");
        Console.Write("]");
    }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
       // JavaScript code for the above approach
       let MAX = 256
 
       // Function to find all anagrams using hashtable
       function findAnagrams(s, p)
       {
           let n = s.length, m = p.length;
 
           // Vector to store all indices of substrings
           // that are anagram of string p
           let ans = [];
 
           // Handling edge cases
           if (n < m || m == 0)
               return ans;
 
           // Hashtables for both strings
           let ms = new Array(26).fill(0), mp = new Array(26).fill(0);
 
           // Initialise the hashtable for string p
           for (let i = 0; i < p.length; i++) {
               mp[p[i].charCodeAt(0) - 'A'.charCodeAt(0)]++;
           }
 
           let i = 0;
           let flag = true;
 
           // Initialise the hashtable
           // for string s for window m
           for (i = 0; i < m; i++) {
               ms[s[i].charCodeAt(0) - 'A'.charCodeAt(0)]++;
           }
 
           // Check if current hashtables are same
           // for current window m
 
           for (let j = 0; j < 26; j++)
               if (mp[j] != ms[j])
                   flag = false;
 
           // if same, push the index of
           // Starting substring into window m
 
           if (flag)
               ans.push(0);
 
           // Traverse string s with window m
           for (i = m; i < n; i++) {
               ms[s[i - m].charCodeAt(0) - 'A'.charCodeAt(0)]--;
               ms[s[i].charCodeAt(0) - 'A'.charCodeAt(0)]++;
 
               // Check if current hashtables are same
               // for current window m
               if (mp[s[i].charCodeAt(0) - 'A'.charCodeAt(0)] == ms[s[i].charCodeAt(0) - 'A'.charCodeAt(0)]
                   && mp[s[i - m].charCodeAt(0) - 'A'.charCodeAt(0)] == ms[s[i - m].charCodeAt(0) - 'A'.charCodeAt(0)]) {
                   flag = true;
                   for (let j = 0; j < 26; j++)
                       if (mp[j] != ms[j])
                           flag = false;
               }
               else
                   flag = false;
 
               // if same, push the index
               // of starting substring
               // into answer
               if (flag)
                   ans.push(i - m + 1);
           }
 
           // Return the final vector of indices
           return ans;
       }
 
       // Driver program
 
       let txt = "BACDGABCDA";
       let pat = "ABCD";
       let indices = findAnagrams(txt, pat);
       document.write("[ ");
       for (let i of indices)
           document.write(i + " ");
       document.write("]");
 
      // This code is contributed by Potta Lokesh
   </script>

Output

[ 0 5 6 ]

Time complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!