Anagram Substring Search

Given two strings ‘STR’ and ‘PTR’. Find all the starting indices of ‘PTR’ anagram substring in ‘STR’. Two strings are anagram if and only if one string can be converted into another string by rearranging the character.

For example, ‘ABCD’ and ‘ACBD’ are two anagram strings because ‘ACBD’ can be converted into ‘ABCD’ by rearranging the ‘B’ and ‘C’. ’ABA’ and ‘ABB’ are not anagram because we can’t convert ‘ABA’ to ‘ABB’ by rearranging the characters of particular strings.

‘ABACD’ and ‘CABAD’ are anagram because ‘ABACD’ can be converted into ‘CABAD’ by rearranging the first ‘A’ with ‘C’ and second ‘A’ with ‘B’.

Note:

Strings ‘STR’ and ‘PTR’ consist only of English uppercases.

Length of string ‘STR’ will always be greater than or equal to the length of string ‘PTR’.

The index is ‘0’ based.

In case, there is no anagram substring then return an empty sequence.

Explanation:

For example, the given ‘STR’ is ‘BACDGABCD’ and ‘PTR’ is ‘ABCD’. Indices are given

0-3 in ‘STR’ index 0,1,2,3 are ‘BACD’ and it is an anagram with ‘ABCD’
1-4 in ‘STR’ index 1,2,3,4 are ‘ACDG’ and it is not anagram with ‘ABCD’
2-5 in ‘STR’ index 2,3,4,5 are ‘CDGA’ and it is not anagram with ‘ABCD’
3-6 in ‘STR’ index 3,4,5,6 are ‘DGAB’ and it is not anagram with ‘ABCD’
4-7 in ‘STR’ index 4,5,6,7 are ‘GABC’ and it is not anagram with ‘ABCD’
5-8 in ‘STR’ index 5,6,7,8 are ‘ABCD’ and it is an anagram with ‘ABCD’

Hence there are 2 starting indices of substrings in the string ‘STR’ that are anagram with given ‘PTR’  which are index 0 and 5.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘3*T’ lines represent the ‘T’ test cases.

The first line of each test case contains two integers ‘N’ and ‘M’. Where ‘N’ denotes the number of characters in ‘STR’ and ‘M’ denotes the number of characters in ‘PTR’.

The second line of each test case contains the string ‘STR’ on a separate line . 

The third line of each test case contains the string ‘PTR’ on a separate line. 

Output Format

For each test case, print a sequence of all the starting indices of the anagram substrings present in the given word/string ‘STR’.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 50
1 <= 'N', 'M' <= 10 ^ 4

Where ‘T’ is the total number of test cases, ‘N’ denotes the number of characters in the first given string ‘STR’ and ‘M’ denotes the number of characters in the second given string ‘PTR’. Strings ‘STR’ and ‘PTR’ only consist of English uppercase alphabets.

Time limit: 1 second.