All submissions for this problem are available.
Hey, you've got a new mission! This time your client ask you to write a editor and it should run fast! However the client's request is somehow strange, but they give a lot of money so your boss ask you to finish it as fast as possible.
This editor deal with a string S. And the length |S| of the string S would never be smaller than 10. This editor must support the following 7 operations quickly. Here the string would be indexed starting at 0.
- INSERT_LEFT c : insert character c at the beginning of S
- INSERT_RIGHT c : insert character c at the end of S
- INSERT_MIDDLE c : insert character c at the middle of S (before the (|S| div 2)-th character)
- DELETE_LEFT : delete the first character of S
- DELETE_RIGHT : delete the last character of S
- DELETE_MIDDLE : delete the middle character of S (the (|S| div 2)-th character)
- QUERY q : print how many times the string q occur in S. (overlap is allowed)
Here div means integer division, that is, |S| div 2 = floor(|S| / 2).
The first line of input contains the initial string SInit. The second line contains one integer Q, denoting the number of operations. Then each of the next Q lines contains an operation with the format mentioned above.
For each QUERY operation, print the answer in a line.
- 1 ≤ Q ≤ 150000 (1.5 * 105)
- |SInit| = 10
- SInit, q contain only lower Latin letters ('a'-'z').
- c is a lower Latin letter ('a'-'z').
- The total length of the string q over all the queries does not exceed 1500000 (1.5 * 106).
- The DELETE_LEFT, DELETE_RIGHT, DELETE_MIDDLE operations do not appear when |S| = 10.
Input: bbabaaaaab 12 INSERT_MIDDLE b INSERT_LEFT b INSERT_MIDDLE b INSERT_MIDDLE b INSERT_RIGHT a INSERT_LEFT a INSERT_MIDDLE b INSERT_LEFT a INSERT_MIDDLE a QUERY bbaaa DELETE_MIDDLE DELETE_MIDDLE Output: 1
In the sample, the string |S| will be changed as follows:
bbabaaaaab (SInit) bbababaaaab (after INSERT_MIDDLE b) bbbababaaaab (after INSERT_LEFT b) bbbababbaaaab (after INSERT_MIDDLE b) bbbababbbaaaab (after INSERT_MIDDLE b) bbbababbbaaaaba (after INSERT_RIGHT a) abbbababbbaaaaba (after INSERT_LEFT a) abbbababbbbaaaaba (after INSERT_MIDDLE b) aabbbababbbbaaaaba (after INSERT_LEFT a) aabbbabababbbaaaaba (after INSERT_MIDDLE a) aabbbababbbbaaaaba (after DELETE_MIDDLE) aabbbababbbaaaaba (after DELETE_MIDDLE)
For QUERY bbaaa, this string occurs once. It is shown in boldface type.
|Tags||april13, hard, suffix-array, treap, wjmzbmr|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.