daihan's blog

How to solve this problem ?
By daihan, 5 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any constraints on the size of the input strings?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    length <= 10^2

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 5   Vote: I like it -13 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        lowercase letter and one letter can be repeated more than one

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Is there any constraint for the total number of letters in all N strings and the total number of letters in all q queries?

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The following is a trie-based C++14 solution for the problem. 1. You can read about retrieval data structure (trie) in GeeksforGeeks.

→ Reply