Find strings containing a certain substring dynamically with queries

Правка en3, от Robbinb1993, 2021-04-21 18:09:46

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 (big) data set that is changing dynamically.

Теги strings

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Robbinb1993 2021-04-21 18:09:46 6 Tiny change: 'ine for a data set ' -> 'ine for a (big) data set '
en2 Английский Robbinb1993 2021-04-21 18:08:23 98
en1 Английский Robbinb1993 2021-04-21 18:06:17 585 Initial revision (published)