Пропозиція виправлення орфографії#3100
Підказка щодо написання — це частина програми для перевірки правопису, яка генерує набір правдоподібних замін для слів, що ймовірно написані з помилками. Один зі способів оцінити ймовірність таких замін — обчислити відстань редагування між даним словом із помилкою та кожною заміною. Відстань редагування між двома словами — це загальна кількість операцій редагування, які потрібно виконати, щоб перетворити одне слово на інше. Зазвичай такі редагування включають вставку, видалення та заміну одного символу, а також допускається транспозиція послідовних символів.
Наприклад, для слова "wonder", якщо видалення застосовується до символу 'o', це слово перетвориться на "wnder". Якщо заміна на 'a' виконується в 'o', воно стане "wander". Якщо застосувати транспозицію до "er", отримаємо "wondre".
У цій стратегії відстані редагування ступінь подібності між двома словами визначається їхньою мінімальною відстанню редагування. Якщо мінімальна відстань редагування між word_1 та word_2 менша, ніж між word_1 та word_3, то word_1 більше схоже на word_2, ніж на word_3. Отже, word_2 — краща підказка щодо написання для word_1 порівняно з word_3.
Припустимо, ви працюєте у компанії-розробнику програмного забезпечення, яка має створити прототип програми підказок щодо написання. Цей прототип буде частиною текстового процесора. Вимога полягає у використанні стратегії відстані редагування для підказок щодо написання. Однак операція заміни символа має бути адаптована для кращого відображення типових помилок набору тексту. Вартість заміни одного символа на інший залежить від їхнього розташування на клавіатурі. Якщо символи розташовані близько на клавіатурі, вартість лише половина стандартної вартості заміни. З цією метою заміни поділяються на близьку (near-substitution) та далеку (far-substitution). Їхня вартість складає, відповідно, та . Вартість вставки, видалення та транспозиції — по . Додатково програма має бути досить швидкою, щоб уміститись у ліміт часу, встановлений вашим менеджером. Для цього прототипу обрано англійську розкладку клавіатури QWERTY.
Мета
Згенеруйте оптимальні підказки щодо написання для кожного вхідного слова, причому кожна оптимальна підказка — це слово зі словника, яке має найменшу відстань редагування до даного слова. Ліміт часу для слів із помилками — не більше хвилин.
Вхід подається через стандартний ввід і складається з частин. Кожна з цих трьох частин закінчується порожнім рядком.
У першій частині міститься набір правил близької заміни (near-substitution), кожне правило — в окремому рядку. Кожен рядок складається з двох полів, розділених пробілом. Загальна кількість правил — не більше .
Перше поле — символ, який можна близько замінити іншими символами.
Друге поле — послідовність символів, якими можна близько замінити символ із попереднього поля. У цьому полі немає пробілів.
Символи, які можуть з'являтись у цій частині, — ті, які можна набрати на звичайній англійській клавіатурі: літери, цифри та деякі розділові знаки, без пробілів чи табуляцій. Ось їх перелік.
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789' !@#$%^6*()-_=+|[{}];:'",<.>/?
Друга частина — список слів зі словника, по одному в рядку. Загальна кількість слів не перевищує .
Допустимі символи для слів словника — алфавітні символи та апостроф (').
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
Третя частина — список слів, для яких потрібно запропонувати підказку, кожне слово у новому рядку. Загальна кількість слів не перевищує .
Символи, що можуть бути у цій частині — ті самі, що й у першій частині: алфавіт, цифри та деякі розділові. (Див. першу частину).
Оскільки кожна з трьох частин закінчується порожнім рядком, третій порожній рядок сигналізує про закінчення вводу.
Для кожного слова з третьої частини виведіть один рядок, що містить компоненти, розділені двокрапкою:
Перше — оригінальне введене слово.
Друге — мінімальна відстань редагування між введеним словом та рекомендованим(-и) словом(-ами).
Третє — список рекомендованих слів через пробіл у зростаючому порядку, без зайвого пробілу після останнього слова.
Додаткове пояснення
У прикладі вводу правил близької заміни (рядки 1-5), слів у словнику (рядки 7-16), слів, яким потрібно запропонувати підказку (рядки 18-29).
У прикладі виводу — рядків для відповідних вхідних слів.
Для 1-го слова мінімальна відстань редагування між x та його підказками (A B Z a b) — . Усі вони — далекі заміни.
Для 2-го слова мінімальна відстань редагування між s та підказкою (a) — — це близька заміна за першим правилом.
Для 3-го слова мінімальна відстань редагування між z та підказками (A Z a) — , за першим чи п'ятим правилами.
Для 4-го слова мінімальна відстань редагування — , тобто одна далека заміна і одне видалення.
Для 5-го слова вона дорівнює : витрати для xxx і (A B Z a b) — дві операції видалення й одна далека заміна; для xxx та ABC — три далекі заміни.
Для 6-го слова: витрати між angre й anger — одна транспозиція; між angre та (angle angry) — одна далека заміна.
Для 7-го і 8-го слова ситуація схожа. Для 7-го слова — одна далека заміна. Для angrt й anger — дві близькі заміни (r замінено на e і t на r) згідно з четвертим правилом близької заміни.
Для 9-го слова слово повністю збігається зі словником, тому витрати — .
Для 10-го й 11-го слова їхні витрати — по одній транспозиції.
Для 12-го слова витрати між CAB і (A B) складаються з двох видалень; між CAB і (ABC) — видалення та вставлення. Зауважте, це не походить із двох транспозицій від CAB до ACB і далі до ABC.
Приклад 1