Задача № 2
Расстояние между словами
Будем называть словом любую последовательность букв русского алфавита. За одну операцию разрешается сделать одно из двух действий:
- убрать из слова одну любую букву;
- добавить в любое место слова любую букву.
За какое наименьшее количество таких операций можно из слова ПРИКОЛ получить слово ПОИСК?
Решение:
Эта задача относится к нахождению редакционного расстояния (или расстояния Левенштейна) между двумя словами, но с упрощенными правилами (только удаление и вставка, без замены). Нам нужно найти минимальное количество операций (удалений или добавлений), чтобы превратить одно слово в другое.
Даны слова:
- Исходное слово: ПРИКОЛ
- Целевое слово: ПОИСК
Давайте сравним эти слова и определим, какие буквы нужно удалить из первого слова и какие добавить, чтобы получить второе.
1. Длина слов:
- Длина слова ПРИКОЛ: 6 букв.
- Длина слова ПОИСК: 5 букв.
2. Найдем общие буквы, которые могут остаться в слове и не требуют операций:
Чтобы минимизировать количество операций, мы должны сохранить как можно больше общих букв в том же порядке.
- ПРИКОЛ
- ПОИСК
Общие буквы, которые можно сохранить в правильном порядке:
- П (есть в обоих словах, в начале)
- И (есть в обоих словах)
- К (есть в обоих словах)
Также буква О есть в обоих словах. Давайте посмотрим, как они расположены:
П Р И К О Л
П О И С К
Если мы сохраним П, И, К, то нам нужно будет разобраться с Р, О, Л из ПРИКОЛ и О, С из ПОИСК.
Давайте попробуем найти самую длинную общую подпоследовательность (не обязательно непрерывную).
- ПРИКОЛ
- ПОИСК
Буквы, которые есть в обоих словах и могут быть сопоставлены:
- П (первая буква)
- О (в ПРИКОЛ она пятая, в ПОИСК вторая)
- И (в ПРИКОЛ третья, в ПОИСК третья)
- К (в ПРИКОЛ четвертая, в ПОИСК пятая)
Рассмотрим последовательность букв, которые можно сохранить, чтобы они были в том же относительном порядке:
П _ И К _
П О И _ К
Наибольшая общая подпоследовательность: ПИК. (3 буквы)
Если мы сохраняем П, И, К, то:
- Из ПРИКОЛ нужно удалить: Р, О, Л (3 операции)
- В ПОИСК нужно добавить: О, С (2 операции)
Итого: \(3 + 2 = 5\) операций.
Давайте попробуем другую общую подпоследовательность: ПОК.
П Р И К О Л
П О И С К
Если мы сохраняем П, О, К, то:
- Из ПРИКОЛ нужно удалить: Р, И, Л (3 операции)
- В ПОИСК нужно добавить: И, С (2 операции)
Итого: \(3 + 2 = 5\) операций.
А что если ПОИСК? ПРИКОЛ ПОИСК Общие буквы: П, И, К, О. Порядок: ПРИКОЛ: П (1), Р (2), И (3), К (4), О (5), Л (6) ПОИСК: П (1), О (2), И (3), С (4), К (5) Мы можем сохранить буквы П, О, И, К. ПРИКОЛ: П _ _ _ О _ К ПОИСК: П О И _ К Давайте выделим буквы, которые совпадают и находятся в правильном относительном порядке:
- П (первая в обоих)
- О (в ПРИКОЛ она пятая, в ПОИСК вторая) - здесь порядок нарушается, если мы хотим сохранить П, О, И, К.
Давайте рассмотрим это как задачу нахождения наибольшей общей подпоследовательности (НОП).
Слово 1: ПРИКОЛ
Слово 2: ПОИСК
Буквы, которые можно сохранить, чтобы они были в том же относительном порядке:
- П (первая буква в обоих)
- И (третья в ПРИКОЛ, третья в ПОИСК)
- К (четвертая в ПРИКОЛ, пятая в ПОИСК)
Таким образом, общая подпоследовательность: ПИК. Длина = 3.
Теперь посчитаем операции:
Количество удалений = Длина слова 1 - Длина НОП = \(6 - 3 = 3\).
Количество добавлений = Длина слова 2 - Длина НОП = \(5 - 3 = 2\).
Общее количество операций = Количество удалений + Количество добавлений = \(3 + 2 = 5\).
Давайте проверим это пошагово:
Исходное слово: ПРИКОЛ
- Удаляем Р: ПИКОЛ (1 операция)
- Удаляем О (которая была пятой): ПИКЛ (1 операция)
- Удаляем Л: ПИК (1 операция)
- Добавляем О (после П): ПОИК (1 операция)
- Добавляем С (после И): ПОИСК (1 операция)
Теперь у нас есть ПИК. Нужно получить ПОИСК.
Итого: \(3 + 2 = 5\) операций.
Это соответствует формуле: \( \text{Расстояние} = \text{Длина1} + \text{Длина2} - 2 \times \text{Длина НОП} \).
В нашем случае: \(6 + 5 - 2 \times 3 = 11 - 6 = 5\).
Ответ:
Наименьшее количество операций равно 5.