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 6Input: 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 256using namespace std;// Function to find all anagrams using hashtablevector<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 programint 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 textimport 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 textMAX = 256# Function to find all anagrams using hashtabledef 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 programif __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 textusing 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/anagram-substring-search-or-search-for-all-permutations-set-2/ […]
… [Trackback]
[…] Find More Info here to that Topic: geeksforgeeks.org/anagram-substring-search-or-search-for-all-permutations-set-2/ […]