2017-10-29 03:58

# K-th good string

10

Problem Description
One day, Lord gave you a string S. Let’s define the pair(x, p) represent the substring S[p-x+1,p-x+2,…,p]. The index of S counts from 0. Then, Lord will tell you some information about this string.

There are three types of the information:
1. Lord will give you a pair(x, p) and then says I think the substring is good.(Only consider the substring (x, p) is good, not include the substring of (x, p))
2. Lord will give you a pair(x, p) and then says I think the substring is not good.
3. Lord will give you a pair(x, p) and a integer K, then you should answer the length of the K-th good string. The K-th good string means that if you list all the distinct good strings which contain pair(x, p) as suffix, then sort them by their length in ascending order, the K-th string is K-th good string.

Now, can you hold the information from Lord? Yon can consider all the substring is not good initially.

Input
First line is a integer T, means the number of test case, T<=10.

In every test case, there is a string S in the first line, composed by lowercase letters, |S|<=100000.

An integer q in the second line (q<=200000), and q lines follow. Every line has an integer t, means the type of the message. If t equals 3, then three integers x, p, K follow, else two integers x, p follow.

The pair (x, p) will always represent a substring of S.

Output
For each case, output “Case #k:” one line first, where k means the case number count from 1.

For every message of type 3, print the answer one line. If there is no such K-th good string, print -1.

Sample Input
1
aaaaa
4
2 1 0
1 3 2
3 2 4 1
3 4 3 1

Sample Output
Case #1:
3
-1

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享
• 邀请回答