| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Сколько нужно перестановок |
| Автор: xTr1m 10.12.2011, 14:18 |
| Доброго времени суток. Есть такая задача. Есть слово А и слово Б, можно удалить или добавить букву в А. Нужно определить можно ли двумя такими операциями из А делать Б. То есть из слова "Кто" можно сделать "Кот" (убрать букву "т" и поставить букву "т" в конец) В голову пришло только 1) проверить на количество букв, если разница больше, чем один символ, то нельзя. 2) проверить пересечение букв, если разница больше, чем в одну букву, то нельзя. 3) сделать из слов два набора (уникальных множества) букв, пройтись по набору и узнать количество несоответствий. Но мне кажется, должен быть путь короче =)) Спасибо. |
| Автор: maxdiver 10.12.2011, 23:25 | ||
| Ну количества букв - это хорошее отсечение, но, так или иначе, решение должно сводиться к сравнению строк: одни только количества букв не говорят о равенстве строк. Достаточно быстрое решение может быть таким: сгенерируем два множества: множество всех слов, которые можно получить из А, и множество всех слов, которые можно получить из Б. Если у этих двух множеств есть общий элемент - то ответ ДА, иначе - НЕТ. Если говорить о скорости решения (хотя автор не озвучил никаких ограничений на длину слов), то прямо в таком "наивном" виде оно имеет асимптотику O (n^2 log n) - если явным образом строить всевозможные строки и сортировать их. (где n - длина строк) Т.е. для строк длины порядка 1000 это решение сгодится. Впрочем, это решение нетрудно довести до оптимального времени O(n) в среднем, воспользовавшись техникой хеширования: 1) строки будем хешировать обычным полиномиальным хешом:
где A[i] - это код i-го символа строки А, p - некоторое небольшое число, q - некоторое большое число. 2) легко научиться считать за O(1) хеш от строки, полученной вставкой в какую-либо позицию какого-либо символа (для этого достаточно только предпосчитать HASH от всех префиксов и суффиксов строки A) 3) построив за O(n) два множества хешей, нам надо проверить, есть ли в них совпадающие элементы. Для этого можно воспользоваться структурой данных hash-set, которая обеспечивает нам O(1) в среднем на одну операцию, что и даст нам итоговые O(n). |
| Автор: xTr1m 11.12.2011, 13:14 |
| Спасибо огромное. |