MMRY - Editorial

PROBLEM LINK:

Practice
Contest

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.

//