Find strings containing a certain substring dynamically with queries

Revision en2, by Robbinb1993, 2021-04-21 18:08:23

Hi,

For this problem I have a set S with initially 0 strings.

There are three types of queries:

  1. Add a string to set S with id = queryId.
  2. Remove the string from set S with id = removeId.
  3. Read a string M and print all strings in set S that have M as substring.

Let N be the size of S.

How would I solve this efficiently? I hope to reach a complexity of O((length of search string) + N) for query 3 and O(length of string) for queries 1 and 2. Is this possible, with for example a suffix tree?

I would like to use this for a fast search engine for a data set that is changing dynamically.

Tags strings

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Robbinb1993 2021-04-21 18:09:46 6 Tiny change: 'ine for a data set ' -> 'ine for a (big) data set '
en2 English Robbinb1993 2021-04-21 18:08:23 98
en1 English Robbinb1993 2021-04-21 18:06:17 585 Initial revision (published)