Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 20 Feb, 2021

Moderate

```
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’.
```

```
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.
```

```
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.
```

```
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.
```

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

```
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
```

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.

- We will iterate over all the permutations of ARR.
- Store them in a set

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

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

- 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 .
- We will maintain a number ‘ANS’ which stores the number of good substrings.
- Divide the substring into M parts of each length K .
- Hash all the parts using a polynomial hash.
- Compute the hash of the substring as the sum of hashes of all M parts.
- If the hash is equal to the hash of the ARR increment the ANS by 1.

Similar problems