CF2041I.Auto Complete

你正在设计一个炫酷的新文本编辑器，并希望为其添加一个智能的自动补全功能，以帮助用户节省时间。其工作方式如下：如果用户输入 "App"，你的编辑器会神奇地建议单词 "Application"！更棒的是，用户还可以个性化设置在你的编辑器中自动补全的单词。

你的编辑器将支持 4 种操作（假设当前编辑器中的文本为 $t$）：

1. 添加一个自动补全模式 $p_i$。
2. 删除一个自动补全模式 $p_i$。
3. 在 $t$ 的末尾追加一个字符串 $s$。
4. 从 $t$ 的末尾删除 $c$ 个字符。注意，如果 $c$ 大于 $t$ 的长度，则将 $t$ 中的所有字符都删除。

每次操作后，你的编辑器应当建议一个自动补全候选模式 $i$，其需满足以下条件：

1. 字符串 $p_i$ 的前缀等于 $t$。
2. 如果有多个 $p_i$ 满足，选择最长的那个。
3. 如果仍有多个 $p_i$ 满足，选择字典序最小的那个。
4. 如果仍有多个 $p_i$ 满足，选择编号最小的那个。

为简化问题，对于每次操作，输出建议的自动补全模式的编号。如果没有匹配的模式，输出 $-1$。例如，假设有三个候选："alice"、"bob" 和 "charlie"，编号分别为 1、2、3。起初屏幕上没有任何内容，因此应建议 "charlie"（3），因为它最长。然后，假设用户输入了 "b"，你应建议 "bob"（2），因为它是唯一以 "b" 开头的。最后，假设用户输入了 "body"，你应输出 $-1$，因为没有匹配的模式。

第一行包含一个整数 $n$，接下来有 $n$ 行，每行包含一个操作。

共有四种操作类型：

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

添加操作后跟一个整数 $i$ 和一个模式 $p_i$，表示用户希望添加编号为 $i$ 的模式。删除操作后跟一个整数 $i$，表示用户希望从模式集合中删除 $p_i$。追加操作后跟一个字符串 $s$，表示用户将 $s$ 追加到 $t$ 的末尾。回退操作后跟一个整数 $c$，表示用户从 $t$ 的末尾删除 $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$ 可以包含任何可打印字符，但不包含空格字符（ASCII 编号范围为 $33$ 到 $126$）
• 每次添加操作的编号 $i$ 是唯一的
• 每次删除操作的编号 $i$ 保证有效
• 每个编号 $i$ 满足 $0\le i \le n$

程序应输出 $n$ 行。对于每次操作，输出一个整数 $i$，表示该操作后建议的自动补全模式编号。如果没有满足条件的 $p_i$，输出 $-1$。

由 ChatGPT 4.1 翻译