To Queue or not to Queue
All submissions for this problem are available.
Chef has a string S. Initially, this string is empty. Also, Chef has a sequence of operations. Each operation is of one of the following two types:
- add character to the end of the string S, so the length of S increases by 1.
- delete the first character of S, so the length of S decreases by 1.
After each operation Chef asks you the number of distinct substrings of the current string S. Please answer his questions!
The first line of input contains Q - the number of operations. Then Q lines follow, each of these lines describes the operation.
- Add operation is of the form "+ C", where C is a lowercase English letter.
- Delete operation is of the from "-".
It is guaranteed that after each operation, the length of S is a positive integer.
Just to make the size of your output smaller, Chef asks you the sum of answers of all Q operations modulo 1000000007.
So, print a single integer - the sum of answers for all operations (the sum of Q numbers) modulo 1000000007.
1 ≤ Q ≤ 1000000
Input: 8 + a + b + a + a - - - + a Output: 27
In the first test case the string S transforms as follows:
- After the first operation S = a. The number of distinct substrings is 1: a.
- After the second operation S = ab. The number of distinct substrings is 3: a, b, ab.
- After the third operation S = aba. Answer is 5: a, b, ab, ba, aba.
- After the fourth operation S = abaa. Answer is 8: a, b, ab, ba, aa, aba, baa, abaa.
- After the fifth operation S = baa. Answer is 5: a, b, ba, aa, baa.
- After the sixth operation S = aa. Answer is 2: a, aa.
- After the seventh operation S = a. Answer is 1: a.
- After the eighth operation S = aa. Answer is 2: a, aa.
The sum is 1 + 3 + 5 + 8 + 5 + 2 + 1 + 2 = 27, 27 modulo 1000000007 = 27, so, you should print 27.
|Tags||gerald, hard, sept13, strings, suffix-trees|
|Time Limit:||3 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.