P4407 [JSOI2009] Electronic Dictionary

When looking up a word in an English dictionary, people may not know the exact spelling and only know an incorrect approximate spelling. This can be frustrating and waste a lot of time. An electronic dictionary with fuzzy search can help: the user enters a string, and the dictionary returns a few words with the minimum edit distance to that string for the user to choose from. The edit distance between string $a$ and string $b$ is defined as the minimum number of the following editing operations needed to transform $a$ into $b$ or $b$ into $a$: 1. Delete a letter at some position in the string. 2. Insert a letter at some position in the string. 3. Replace the letter at some position in the string with another letter. The JSOI team is developing an electronic dictionary. You need to help implement a counting module for the fuzzy search function: for a query string, if it is a word, return $-1$; if it is not a word, return how many words in the dictionary have edit distance $1$ from it.

The first line contains two positive integers $N$ and $M$. The next $N$ lines each contain one string; the $(i+1)$-th line is the word $W_i$, with length from $1$ to $20$. Then the next $M$ lines each contain one string; the $(i+N+1)$-th line is the query string $Q_i$. The length of each query string is from $1$ to $20$. Each of $W_i$ and $Q_i$ consists of lowercase letters. There are no extra spaces in the input.

Output $M$ lines. The $i$-th line contains an integer $X_i$: - $X_i = -1$ means $Q_i$ is a word in the dictionary. - Otherwise, $X_i$ is the number of dictionary words whose edit distance from $Q_i$ is $1$.

Sample explanation: - `abcd` appears in the word list. - The edit distance between `abc` and each of `abcd` and `aabc` is $1$. - The edit distance between `abcdd` and each of `abcd`, `abcde`, and `abced` is $1$. Constraints and Notes: - All words are distinct, but query strings may repeat. - For $50\%$ of the constraints, $N, M \le 10^3$. - For $100\%$ of the constraints, $N, M \le 10^4$. Translated by ChatGPT 5