ADAJOBS - Ada and Jobs
As you might already know, Ada the Ladybug has a huge TODO-list. Sometimes she inserts a new job into her TODO-list and sometimes she is wondering whether there is a job (in her TODO-list), which she wants to do now. She doesn't require the whole job to be there, perhaps just a part of it.
Can you create a program which would serve her? That means it either inserts a new job into her TODO-list or answers whether there exists a word (in her TODO-list) which is a substring of given word.
The first line of input containts Q, the number of queries.
The next Q lines contains a number 0 ≤ t ≤ 1 and nonempty string s. If t is equal to 0 then it is inserion query, otherwise it is question query. s consists of lowercase characters only.
The sum of lengths of queries of both types doesn't exceed 106 (that means the total sum of lengths of strings will be at most 2*106)
NOTE: All newly added jobs will be distinct.
For each query of type 1, print either YES, if there is already a substring in the TODO-list and NO otherwise.
12 0 cat 1 dogville 0 dog 1 dogville 1 gooutwithcat 1 gooutwithcrocodile 1 fancyconcatenation 0 crocodile 1 lacoste 1 gooutwithcrocodile 1 catalanreferendum 1 rocodile
NO YES YES NO YES NO YES YES NO
@♥☻♥ David ♥☻♥: I'm afraid that nope :'( It seems to be O(N) for checking query. The statement is done in such ugly way, that it alows even very long strings and even a lot of very short strings. So there shall be linear-like (or at most some "low" logarithm) for both - inserting and checking [or well, linear-like in other possible approach than this] :) Good Luck & Have Nice day ^_^
♥☻♥ David ♥☻♥:
@morass: Thanks for replying.
@♥☻♥ David ♥☻♥: Good day to you, well not sure whether I understand you question. From what I understood then ... yes you have to check all words (till now) [whether they are substring of query] but you can (obviously) stop at the first one)
♥☻♥ David ♥☻♥:
Do we have to check all substrings of query with the existing TODO ?? :(.Last edit: 2017-10-19 13:39:12
Last edit: 2017-10-13 04:58:44