← 返回题目列表

Codeforces · 2041/I

I. 自动完成

中文机器翻译题面 查看原题

您正在设计一个时髦的新文本编辑器,并且想要添加一个漂亮的自动完成功能来帮助用户节省时间。它的工作原理如下:如果用户输入“App”,您的编辑器会神奇地建议单词“Application”!更好的是,用户可以个性化编辑器中自动完成的单词。

你的编辑器将支持4种操作(假设你的编辑器中当前的文本是$$$t$$$):

1. 添加自动完成模式$$$p_i$$$。
2. 删除自动完成模式$$$p_i$$$。
3. 将字符串 $$$s$$$ 附加到 $$$t$$$ 的末尾。
4. 删除$$$t$$$末尾的$$$c$$$字符。请注意,如果 $$$c$$$ 大于 $$$t$$$ 的长度,则删除 $$$t$$$ 中的所有字符。

在每个操作之后,您的编辑应该建议一个符合以下条件的自动完成候选 $$$i$$$:

1. 字符串$$$p_i$$$ 的前缀等于$$$t$$$。
2. 如果有多个$$$p_i$$$,则选择最长的一个。
3. 如果还有多个$$$p_i$$$,则选择字典顺序最小的一个。
4. 如果还有多个$$$p_i$$$,则选择ID最小的一个。

例如,假设我们有三个候选:“alice”、“bob”和“charlie”,ID 分别为 1、2 和 3。起初,屏幕上没有任何内容,因此应建议“charlie”(3),因为它最长。然后,假设用户输入“b”。您应该建议“bob”(2),因为它是唯一以“b”开头的。最后,假设用户输入“body”。您应该打印 -1,因为没有匹配的模式。

输入

第一行包含一个整数 $$$n$$$,后面是 $$$n$$$ 行,每行包含一个操作。

有四种类型的操作:

1.$$$i$$$$$$p_i$$$
2.$$$i$$$
3.$$$s$$$
4.$$$c$$$

- $$$1 \leq n \leq 10^6$$$
- 所有 $$$p_i$$$ 和 $$$s$$$ 中的字符总数不超过 $$$2\times 10^6$$$。
- $$$1 \leq c \leq 2\times 10^6$$$
- 字符串 $$$p_i$$$ 和 $$$s$$$ 可以包含任何可打印字符,但不包括所有空格字符(范围从 $$$33$$$ 到 $$$126$$$ 的 ASCII 数字)。
- 每个添加操作的 ID $$$i$$$ 都是唯一的。
- 每次删除的 ID $$$i$$$ 保证有效。
- 每个 ID $$$i$$$ 满足 $$$0\le i \le n$$$。

输出

程序应输出 $$$n$$$ 行。对于每个操作,输出一个整数 $$$i$$$,这意味着在该操作之后,$$$p_i$$$ 是建议的自动完成候选者。如果没有符合要求的$$$p_i$$$,则输出-1。

示例

输入 #1

6
add 1 pattern1_alice
add 2 pattern2_bob
add 3 pattern3_charlie
append pattern
append 2_bobabc
backspace 3

输出 #1

1
1
3
3
-1
2

输入 #2

6
append pattern
add 1 pattern1_alice____
add 2 pattern2_bob______
add 3 pattern3_charlie__
delete 1
delete 2

输出 #2

-1
1
1
1
2
3