Условие
ГРУПА A, ЗАДАЧА A. ПРОВЕРКА НА ПРАВОПИС
---
Проверка на правопис се извършва като думата подлежаща на корекция се проверява в множество от предварително въведени думи (речник). Ако дадена дума не се среща в речника, се опитваме да намерим най-близките до нея.
Популярна техника за сравняване на сходство между две думи е намиране на число което наричаме разстояние между дадените думи. Това число определя броя на промените, които трябва да се направят, за да се превърне едната дума в другата. Промяна се счита едно от следните: добавяне, изтриване или смяна на буква с друга.
Примери за разстояние между две думи:
Distance(book, books) -> 1
Distance(book, boo) -> 1
Distance(books, boo) -> 2
Distance(book, cake) -> 4
Вход:
На първият ред от стандартния вход е даден броя на думите (N) за проверка. Следващите 2 x N реда съдържат двойки думите, отделени с нов ред.
Изход:
За всяка двойка думи изведете разстоянието между тях.
Примерен вход:
4
book books
book boo
books boo
book cake
Примерен изход:
1
1
2
4
« Предходна страница
Решение
Въпрос