QUESTION

Input 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. \nExpected time complexity is O(n).

“TESTCASE_1”: “BACDGABCDA\nABCD\n###—###SEPERATOR—###—\nFound at Index 0\nFound at Index 5\nFound at Index 6”, “TESTCASE_2”: “AAABABAA\nAABA\n###—###SEPERATOR—###—\nFound at Index 0\nFound at Index 1\nFound at Index 4”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

import java.io.*;
import java.util.*;
public class TestClass
{
    static final int MAX = 256;
    
    // This function returns true if contents
    // of arr1[] and arr2[] are same, otherwise
    // false.
    static boolean compare(char arr1[], char arr2[])
    {
        for (int i = 0; i < MAX; i++)
            if (arr1[i] != arr2[i])
                return false;
        return true;
    }

    // This function search for all permutations
    // of pat[] in txt[]
    static void search(String pat, String txt)
    {
        int M = pat.length();
        int N = txt.length();

        // countP[]:  Store count of all 
        // characters of pattern
        // countTW[]: Store count of current
        // window of text
        char[] countP = new char[MAX];
        char[] countTW = new char[MAX];
        for (int i = 0; i < M; i++)
        {
            (countP[pat.charAt(i)])++;
            (countTW[txt.charAt(i)])++;
        }

        // Traverse through remaining characters
        // of pattern
        for (int i = M; i < N; i++)
        {
            // Compare counts of current window
            // of text with counts of pattern[]
            if (compare(countP, countTW))
                System.out.println("Found at Index " +
                                          (i - M));
            
            // Add current character to current 
            // window
            (countTW[txt.charAt(i)])++;

            // Remove the first character of previous
            // window
            countTW[txt.charAt(i-M)]--;
        }

        // Check for the last window in text
        if (compare(countP, countTW))
            System.out.println("Found at Index " + 
                                       (N - M));
    }

    /* Driver program to test above function */
    public static void main(String args[])
    {
      Scanner sc=new Scanner(System.in);  
      String txt = "";
        String pat = "";
      txt=sc.next();
      pat=sc.next();
        search(pat, txt);
    }
}