spoj
Състезание
Задача
A
Наименование
SPELL CHECK

Условие

ГРУПА 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

« Предходна страница Решение Въпрос