Anagram Search

PHOTO EMBED

Tue Feb 08 2022 12:29:55 GMT+0000 (UTC)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #string #anagramsearch

// Efficient Code : O(m+(n-m) * CHAR)  or  since m<n so, 
// Time : O(n * CHAR),  Aux. Space : Θ(CHAR)

import java.util.*;
import java.io.*;
  
class GFG { 
    
    static final int CHAR=256;
    static boolean areSame(int CT[],int CP[])
    {
        for(int i=0;i<CHAR;i++){
            if(CT[i]!=CP[i])return false;
        }
        return true;
    }
    
    static boolean isPresent(String txt,String pat)
    {
        int[] CT=new int[CHAR];
        int[] CP=new int[CHAR];
        for(int i=0;i<pat.length();i++) {
            CT[txt.charAt(i)]++;
            CP[pat.charAt(i)]++;
        }
        for(int i=pat.length();i<txt.length();i++) {
            if(areSame(CT,CP))return true;
            CT[txt.charAt(i)]++;
            CT[txt.charAt(i-pat.length())]--;
        }
        return false;
    }
    
    public static void main(String args[]) 
    { 
        String txt = "geeksforgeeks"; 
        String pat = "frog";  
        if (isPresent(txt, pat)) 
            System.out.println("Anagram search found"); 
        else
            System.out.println("Anagram search not found"); 
    } 
} 






// Naive Code : O((n-m+1)*m)

import java.util.*;
import java.io.*;
  
class GFG { 
    
    static final int CHAR=256;
    static boolean areAnagram(String pat, String txt,int i) 
    { 
        int[] count=new int[CHAR];
        for(int j=0; j<pat.length(); j++)
        {
            count[pat.charAt(j)]++;
            count[txt.charAt(i+j)]--;
        }
        for(int j=0; j<CHAR; j++)
        {
            if(count[j]!=0)
                return false;
        }
        return true;
    } 
    
    static boolean isPresent(String txt,String pat)
    {
        int n=txt.length();
        int m=pat.length();
        for(int i=0;i<=n-m;i++)
        {
            if(areAnagram(pat,txt,i))
                return true;
        }
        return false;
    }
    
    public static void main(String args[]) 
    { 
        String txt = "geeksforgeeks"; 
        String pat = "frog";  
        if (isPresent(txt, pat)) 
            System.out.println("Anagram search found"); 
        else
            System.out.println("Anagram search not found"); 
    } 
} 
content_copyCOPY

Given a text and a pattern, the task is to find if there is anagram of pattern present in text. The code talks about two solutions to solve the problem.