Given N strings , Then there will be q queries . In each query a string S , you have to determine in how many string ( N given string ) S is a subsequence of that string . For example
N=5
aeh
apoq
xyzq
alpqh
caqwerh
Q=1
ah
ans=3 , because "ah" is a subsequence of aeh , alpqh and caqwerh .
How to solve this problem effeciently . Suppose N=10^5 and Q=3*10^5 , Each string lenght would be <=10^2
Any constraints on the size of the input strings?
length <= 10^2
Any further constraints? All input strings in the given example have lower-case english letters and are composed of distinct letters, i.e. no letter appears more than once in the same string.
lowercase letter and one letter can be repeated more than one
If the string alphabet is restricted to 26 lower-case english letters only, then some letter(s) will have to appear more than once when the size is greater than 26. Does the 100 letters maximum string size apply to the input query strings as well?
Is there any constraint for the total number of letters in all N strings and the total number of letters in all q queries?
The following is a trie-based C++14 solution for the problem. 1. You can read about retrieval data structure (trie) in GeeksforGeeks.