P2292 [HNOI2004] L Language

Punctuation appeared later than writing, so earlier languages had no punctuation. Now you need to process an article without punctuation. An article $T$ consists of lowercase letters. A word $W$ also consists of lowercase letters. A dictionary $D$ is a set of words. We say an article $T$ is understandable under a dictionary $D$ if $T$ can be split into several parts and each part is a word in $D$. For example, if the dictionary $D$ includes the words $\texttt{is}, \texttt{name}, \texttt{what}, \texttt{your}$, then the article `whatisyourname` is understandable under $D$ because it can be split into 4 words: `what`, `is`, `your`, `name`, and each word belongs to $D$. The article `whatisyouname` is not understandable under $D$, but it is understandable under $D' = D \cup \{\texttt{you}\}$. A prefix `whatis` of this article is also understandable under $D$, and it is the longest prefix that can be understood under $D$. Given a dictionary $D$, your program needs to determine whether several articles are understandable under $D$, and output the position of the longest prefix that can be understood under $D$.

The first line contains two integers $n$ and $m$, indicating that the dictionary $D$ has $n$ words and there are $m$ articles to process. The next $n$ lines each contain a string $s$, representing a word in the dictionary $D$. The next $m$ lines each contain a string $t$, representing an article.

For each article in the input, output one line with a single integer, the position of the longest prefix that can be understood under the dictionary $D$.

Explanation for Sample 1 - For the first query, the entire article `whatisyourname` can be understood. - For the second query, the prefix `whatis` can be understood. - For the third query, no prefix can be understood. Constraints - For $80\%$ of the data, it is guaranteed that $m \leq 20$, $|t| \leq 10^6$. - For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 20$, $1 \leq m \leq 50$, $1 \leq |s| \leq 20$, $1 \leq |t| \leq 2 \times 10^6$, and both $s$ and $t$ contain only lowercase English letters. Tips - Pay attention to the impact of input reading on program efficiency. - Note that the string lengths marked in Constraints are per-string lengths, not the sum of lengths. Notes - The testdata is strengthened; the first $80\%$ is the original testdata. Translated by ChatGPT 5