Substring Permutation

PROBLEM STATEMENT

You are given a string S of length N and an array of strings ARR. All the strings in ARR are of the same length K. Your task is to find the number of such sub-strings in the string 'S' that is the concatenation of all the strings of ARR in some order.

For example :

Let ARR = [hot, dog] and S = "hotdoghot", there are two sub-strings that can be obtained by permutation of ARR starting from index 0 -> ‘hotdog’ and starting from the index 3 -> ‘doghot’.

Note :

1. An string C is a substring of string S if it can be obtained by deletion of several characters(possibly zero) from the beginning and the end from a string S.
2. The substring must contain all the strings in ARR only once and without any extra intervening character.

Input Format :

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

The first line of each test case contains three single space-separated integers ‘N’, ‘M’, ‘K’ denoting the size of the string S, length of the array/list ARR and length of each string in ARR. 

The second line of each test case contains string S.

The third line of each test case contains ‘M’ space-separated strings, denoting the elements of the array ARR.

Output Format :

For each test case print the number of substrings that can be formed by some permutation of ARR. 

Output for each test case is printed in a separate line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 1000
1 <= M <= 10
1 <= K <= 100      
String S and all the strings in ARR contain only lowercase English letters.

Time Limit: 1 sec

Approach 1

We will iterate through all the permutations of ARR and store them in a set. Then for each string of length of M*K check if it is there in then set.

The algorithm will be-

We will iterate over all the permutations of ARR.
1. Store them in a set
We will iterate over all the substring of length M*K.
1. We will maintain a number ‘ANS’ that stores the number of good substrings.
2. If the string is in set increment ANS by 1.

Try Problem

Approach 2

ARR is hashed as the sum of the polynomial hash of all the strings in ARR. Each substring of S of length M*K is divided into M strings of length K each and their hash is computed as sum of the polynomial hash of each string of length K.

Polynomial hashing: Link

The algorithm will be-

Hash the all the strings in ARR using the polynomial hash.
Compute the hash of the ARR as the sum of the hash of all the string in ARR.
For each substring of length K*M in S .
1. We will maintain a number ‘ANS’ which stores the number of good substrings.
2. Divide the substring into M parts of each length K .
3. Hash all the parts using a polynomial hash.
4. Compute the hash of the substring as the sum of hashes of all M parts.
5. If the hash is equal to the hash of the ARR increment the ANS by 1.

Try Problem