### PROBLEM LINK:

**Author:** admin5

**Editorialist:** admin5

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Suffix Trie/Tree , Basic String Computations

### PROBLEM:

Your are given **N** string of length **S** (1 \le S \le 18). And **Q** queries, each query you are asked to find out the number of occurrence of string **X** in all **N** strings.

### QUICK EXPLANATION:

You are given **N** strings of length **S**, you can make an array of all **N** strings and then in each query you just need to count the occurrence of given string **X** in all **N** strings.

Complexity of this approach is (N * Q * S)

### DETAILED EXPLANATION:

For all given **N** strings of length **S**, you should build a **Suffix Trie** or **Suffix Tree**. It will take O(N*S) time to build, and you have to build Suffix Trie like that each node contain the occurrence of itself.

Once Suffix Trie is built you are ready to answer for **Q** queries, for each query you just need to check whether it is belong to Suffix Trie or not. If is is not belong to Suffix Trie then answer is **0** otherwise the answer is occurrence of last node of string in Suffix Trie.

Complexity of this approach is O(N*S + Q*S).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.