Find strings containing a certain substring dynamically with queries
Difference between en1 and en2, changed 98 character(s)
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.

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)