#P17809. [ICPC 2019 Nanchang R] Dynamic Suffix Array
[ICPC 2019 Nanchang R] Dynamic Suffix Array
Problem Description
In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used, among others, in full-text indices, data compression algorithms and within the field of bibliometrics.
Assume is a string, let's denote as the substring of ranging from to and denote suffix as .
The suffix array of is now defined to be an array of integers providing the starting positions of suffixes of in lexicographical order. This means, an entry contains the starting position of the -th smallest suffix in and thus always holds for each .
Now there is an empty string , you need to maintain its suffix array dynamically. There will be events of the two kinds below:
1 c: Append a character at the end of , it is guaranteed that is chosen uniformly at random from lower-case english letters to .2 k(): You need to report the position of in the current suffix array of , which means you need to report the rank of suffix .
Please write a program to process these events efficiently.
Input Format
The first line of the input contains an integer (), denoting the number of events.
For the next lines, each line describes an event. It is guaranteed that the first event is of the first type, and the last event is of the second type.
Output Format
For each event of the second type, output an integer denotes the answer in a single line.
10
1 t
1 s
2 2
1 r
1 w
1 f
1 t
2 2
1 q
2 2
1
3
4