| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 64 MB | 1 | 0 | 0 | 0.000% |
При наборе текста довольно часто возникают опечатки из-за неправильного нажатия на клавиши. Например, некоторые буквы оказываются заменены на другие, появляются лишние буквы, некоторые буквы исчезают из слов. В большинстве случаев эти опечатки можно исправить автоматически. В частности, существует метод проверки орфографии, основанный на поиске в словаре слов, похожих на проверяемые.
Два слова называются похожими, если можно удалить из каждого слова не более одной буквы так, чтобы слова стали одинаковыми, возможно пустыми. Например, слова "spot" и "sport" похожи, так как одно и то же слово "spot" можно получить из первого слова без удаления букв, а из второго --- удалением буквы "r".
Требуется написать программу, которая для каждого слова проверяемого текста определяет количество похожих на него слов в словаре.
В первой строке входного файла через пробел записаны натуральные числа% $N \ge 1$ --- общее количество слов в словаре и $M \ge 1$ --- количество слов в проверяемом тексте ($N+M \le 20,000円$) В последующих $N$ строках записаны слова, входящие в словарь, по одному на строке. Все слова словаря различны. Далее следуют $M$ строк, в которых записаны слова проверяемого текста, по одному слову в строке.
Слова состоят из строчных и прописных букв латинского алфавита (прописные и строчные буквы считаются различными). Любое слово состоит не менее чем из одной и не более чем из 12 букв.
Для каждого слова из текста выведите в выходной файл строку, содержащую это слово, далее через пробел количество слов из словаря, на которые оно похоже. Если в словаре имеется единственное похожее слово, то также выведите в этой строке это слово (через пробел).
5 8 father and or mother a Father and mather go o for e walk
Father 1 father and 1 and mather 2 go 1 or o 2 for 1 or e 1 a walk 0