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.