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.
Input
The first line of input contains 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 insertion 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)
Output
For each query of type 1, print either YES, if there is already a substring in the TODO-list and NO otherwise.
Example Input
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
Example Output
NO YES YES NO YES NO YES YES NO
hide comments
zhouchenghao__:
2021-09-25 09:13:24
Can a string type store a string with a length of 10^6? |
|
crypter472:
2020-07-06 19:19:39
Nice problem! really learned a lot. |
|
spojmaster_9:
2019-08-24 03:51:34
@morass: Im new to aho-corasick, can you take a look to my code and tell why i get WA? 24288131
|
|
DOT:
2018-09-02 12:12:06
Anyone struggling with this, read about Aho-Corasick algorithm. Apparently, this algorithm forms the basis for even linux's grep command. |
|
morass:
2018-06-28 14:41:55
@rishabh1322: Good day to you,
|
|
rishabh1322:
2018-04-24 11:17:21
0 crocodile
|
|
morass:
2018-03-30 12:25:42
@Tanzir Islam: You were right, than you! I modified the statement! |
|
Tanzir Islam:
2018-03-10 16:42:38
@morass Can you please check if this constraint stated in the input section " All newly added jobs will be distinct." correct? I got a WA because of this issue and fixed it. Then I submitted a code which checks if the same string has been given as job before and asserts false in that case. The code gets RTE. So I think there are strings in your input file which are not distinct and given as jobs. |
|
morass:
2018-02-18 12:33:25
@amanvirat: Good day to you. Well sadly it isn't near required complexity. The part where you are printing is at least O(multiplocation of lengths of patterns and texts) :'( |
|
amanvirat:
2018-02-16 19:25:19
@morass can you tell why this 21179409 give TLE.
|
Added by: | Morass |
Date: | 2017-10-10 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |