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.

Example Input

0 cat
1 dogville
0 dog
1 dogville
1 gooutwithcat
1 gooutwithcrocodile
1 fancyconcatenation
0 crocodile
1 lacoste
1 gooutwithcrocodile
1 catalanreferendum
1 rocodile

Example Output


hide comments
julkas: 2018-01-04 15:10:32

@morass Thank you. It was my bug.

Last edit: 2018-01-04 15:10:48
morass: 2018-01-04 14:16:42

@julkas: Good day to you and happy new year. Is there something particular I shall investigate? The test-case your RTE on seems to have correct number of lines, with [0,1] digit and nonempty sequence of lowercase characters, whose sum is also low enough.

julkas: 2018-01-03 15:41:47

@morass Can you check input format, please.
My best regards and Happy New Year!

morass: 2017-12-20 18:56:12

@♥☻♥ David ♥☻♥: Good job, Congratulations :)

alexyu: 2017-12-07 11:56:11

What techniques does this problem require? I am trying to use a suffix automaton but am failing...

♥☻♥ David ♥☻♥: 2017-11-26 16:11:10

@morass: Tons of wrong answer :(.
Finally done :)

Last edit: 2017-12-17 19:59:49
morass: 2017-10-19 17:22:47

@♥☻♥ 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 ♥☻♥: 2017-10-19 17:05:52

@morass: Thanks for replying.
Can you please check my latest submission 20402278 and let me know if I'm on right direction

morass: 2017-10-19 16:56:32

@♥☻♥ 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 ♥☻♥: 2017-10-14 14:02:14

Do we have to check all substrings of query with the existing TODO ?? :(.

Last edit: 2017-10-19 13:39:12

Added by:Morass
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)