P10526 [XJTUPC 2024] Command Line.

There are $n$ pairwise distinct command strings $t_i$ ($1 \leq i \leq n$), each consisting only of lowercase letters. You need to implement a command line that supports command auto-completion. Your input area is a string $s$. It can accept lowercase letters $\text{'a'-'z'}$, the $\text{Tab}$ key (denoted by $\text{'T'}$), the $\text{Enter}$ key (denoted by $\text{'E'}$), and the $\text{Backspace}$ key (denoted by $\text{'B'}$). The rules are as follows: 1. When you receive a lowercase letter $c$, append $c$ to the end of the input area string $s$. 1. When you receive the $\text{Backspace}$ key, it will try to delete the last character: - If the input area string $s$ is empty, do nothing. - If the input area string $s$ is not empty, discard the last character of $s$. 1. When you receive the $\text{Tab}$ key, perform one smart completion on $s$. The completion rules are: - Let the set of command strings with prefix $s$ be $T$. - If $T$ is empty, do nothing. - If $T$ is not empty, set $s$ to $\text{lcp}(T)$. Here $\text{lcp}$ means the longest common prefix, i.e., the longest string that is a prefix of every string in $T$. 1. When you receive the $\text{Enter}$ key, it will try to execute the command $s$: - If there exists a command string $t_i = s$, output the command index $i$. - If there is no command string $t_i = s$, output $-1$. - Whether the execution succeeds or not, clear the input area $s$. Given the input string $p$ that you receive, you need to output the result of each $\text{Enter}$ key execution.

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^6$), the number of command strings and the length of the input string, separated by spaces. The next $n$ lines each contain a string $t_i$ consisting only of lowercase letters, representing a command string. It is guaranteed that $\sum_{i=1}^{n} |t_i| \leq 10^6$ and all command strings are pairwise distinct. The last line contains a string $p$ ($|p|=m$), representing the input string. It is guaranteed that $p$ consists only of $\text{\{'a'-'z', 'T', 'B', 'E'\}}$.

Given the input string $p$ that you receive, you need to output the result of each $\text{Enter}$ key execution.

Initially, the input area string $s=""$. After inputting $\text{'k'}$, the input area string becomes $s="k"$. After inputting $\text{'T'}$, perform smart completion. At this time, $T=\{"kill","killall"\}$, and $\text{lcp}(T)="kill"$. Therefore, the input area string becomes $s="kill"$. After inputting $\text{'B'}$, the input area string becomes $s="kil"$. After inputting $\text{'l'}$, the input area string becomes $s="kill"$. After inputting $\text{'E'}$, since $t_1=s$, you should output $1$. Translated by ChatGPT 5