Query On Strings
All submissions for this problem are available.
Aniket loves strings and hence he keeps expanding his collection of strings. Harsh came up with an idea to tease Aniket. Harsh can ask Aniket to do one of the following operations to his collection of strings (Initially he has an empty collection).
- Add: Add a given string to the collection.
- Ask: Ask if there exists a group of k strings such that they have a common suffix of length l .
- Removei: Remove the string that was added in the ith operation (if the string is not already removed). It is guaranteed that ith operation was an Add operation.
Aniket is tired of the mid-sem exams he has just had. Can you help him do all these operations and find the answers of all Ask operations.
First line of input contains an integer q denoting the total number of operations Harsh does. q lines follow in the following format.
- 1 s Add the string s(all lowercase characters) to Aniket's collection of strings.
- 2 k l Ask if there exists a group of k strings such that they have a common suffix of length l.
- 3 x Remove the string added in the xth operation (if not already removed).
- 1 ≤ q ≤ 105
- 1 ≤ |s| (sum of lengths of all strings added to the collection) ≤ 105
- 1 ≤ k,l ≤ 105
- 1 ≤ x ≤ number of operations done yet
Print the answer to all the Ask operations in different lines. Print "YES" if it exists else print "NO".
Input 1: 9 1 aba 1 accba 2 2 2 2 2 3 1 aaaa 1 ababa 2 3 2 3 1 2 3 2 Output 1: YES NO YES NO
|Tags||easy-medium, npl_nitw, nplq1601, strings, trie|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.