Задача Word2
Під час уроку інформатики два учні, не слухаючи пояснень вчителя, грають в таку гру. Кожен з них в своєму зошиті записує два обраних ними разом слова і намагається за певну кількість ходів з першого слова отримати друге. Виграє той, хто зробить мінімальну кількість ходів. Хід – це одна з таких операцій:1.замінити якийсь символ з першого слова якимось символом другого слова;2. викреслити якийсь символ з першого слова;3. ставити якийсь символ з другого слова після або перед якимось символом першого слова. Наприклад, для перетворення слова “limuzin” в слово “buzina” необхідно виконати такі дії:
| Перетворення | Номер операції | ||
| limuzin imuzin ibuzin ibuzina |
=> => => => |
imuzin ibuzin ibuzina buzina |
2 1 3 2 |
Спробуйте написати програму, яка знаходить мінімальну кількість ходів для перетворення одного заданного слова в інше.
Технічні умови Програма читає з клавіатури дві стрічки довжиною не більше 104 символів кожна і виводить на екран єдине число – мінімальну кількість ходів.
| Приклад | Введення | Виведення |
|
limuzin buzina |
4 |