# Searching 58

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

``````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);
}
}``````