Содержание
- 2. Префикс-функция. Определение Дана строка s [0 .. n – 1]. Требуется вычислить для неё префикс-функцию, то
- 3. Тривиальный алгоритм Непосредственно следуя определению, можно написать такой алгоритм вычисления префикс-функции: Как нетрудно заметить, работать он
- 4. Эффективный алгоритм Первая оптимизация Первое важное замечание – что значение prefix[i + 1] не более чем
- 5. Вторая оптимизация Пойдем дальше – избавимся от явных сравнений подстрок. Для этого постараемся максимально использовать информацию,
- 6. Итак, общая схема алгоритма у нас есть, нерешенным остался вопрос об эффективном нахождении таких длин j.
- 7. Итоговый алгоритм Мы окончательно построили алгоритм, который не содержит явных сравнений строк и выполняет действий. Приведем
- 8. Реализация В итоге алгоритм получился весьма простым и красивым:
- 9. Полезные ссылки - http://e-maxx.ru/algo/prefix_function https://ru.wikipedia.org/wiki/Алгоритм_Кнута_—_Морриса_—_Пратта http://habrahabr.ru/post/191454/
- 11. Скачать презентацию
Префикс-функция. Определение
Дана строка s [0 .. n – 1]. Требуется вычислить
Префикс-функция. Определение
Дана строка s [0 .. n – 1]. Требуется вычислить
Математически определение префикс-функции можно записать следующим образом:
Например, для строки "abcabcd" префикс-функция равна: [0, 0, 0, 1, 2, 3, 0] , что означает:
у строки "a" нет нетривиального префикса, совпадающего с суффиксом;
у строки "ab" нет нетривиального префикса, совпадающего с суффиксом;
у строки "abc" нет нетривиального префикса, совпадающего с суффиксом;
у строки "abca" префикс длины 1 совпадает с суффиксом;
у строки "abcab" префикс длины 2 совпадает с суффиксом;
у строки "abcabc" префикс длины 3 совпадает с суффиксом;
у строки "abcabcd" нет нетривиального префикса, совпадающего с суффиксом.
Другой пример — для строки "aabaaab" она равна: [0, 1, 0, 1, 2, 2, 3].
Тривиальный алгоритм
Непосредственно следуя определению, можно написать такой алгоритм вычисления префикс-функции:
Как нетрудно
Тривиальный алгоритм
Непосредственно следуя определению, можно написать такой алгоритм вычисления префикс-функции:
Как нетрудно
Эффективный алгоритм
Первая оптимизация
Первое важное замечание – что значение prefix[i + 1]
Эффективный алгоритм
Первая оптимизация
Первое важное замечание – что значение prefix[i + 1]
Таким образом, при переходе к следующей позиции очередной элемент префикс-функции мог либо увеличиться на единицу, либо не измениться, либо уменьшиться на какую либо величину. Уже это факт, позволяет сократить асимптотическое время работы алгоритма до - поскольку за один шаг значение могло вырасти максимум на единицу, то суммарно для всей строки могло произойти не более n увеличений на единицу, и, как следствие, не более n уменьшений.
Вторая оптимизация
Пойдем дальше – избавимся от явных сравнений подстрок. Для этого
Вторая оптимизация
Пойдем дальше – избавимся от явных сравнений подстрок. Для этого
Пусть мы вычислили значение префикс-функции prefix[i] для некоторого i. Теперь, если s[i + 1] = s[prefix[i]], то с уверенностью можно утверждать, что prefix[i + 1] = prefix[i] + 1.
Пусть теперь, наоборот, оказалось, что string[i + 1] != string[prefix[i]]. Тогда нам надо попытаться попробовать подстроку меньшей длины. В целях оптимизации хотелось бы сразу перейти к такой (наибольшей) позиции j < prefix[i], что по-прежнему выполняется префикс-свойство в позиции i, то есть string[0 .. j – 1] == string[i – j + 1 .. j].
Действительно, когда мы найдем такую длину j, то нам снова достаточно сравнить символы string[i + 1] и string[j] – если они совпадут, то можно утверждать, что
prefix[i + 1] == j + 1. Иначе нам надо будет снова найти наименьшее значение j, для которого выполняется префикс-свойство, и так далее. Может случиться, что такие значения j кончатся – это происходит, когда j = 0. В этом случае, если string[i + 1] = string[0], то prefix[i + 1] = 1, иначе prefix[i + 1] = 0.
Итак, общая схема алгоритма у нас есть, нерешенным остался вопрос об
Итак, общая схема алгоритма у нас есть, нерешенным остался вопрос об
После столь подробного описания уже становится очевидным тот факт, что это значение k есть не что иное, как значение префикс-функции prefix[j – 1], которое уже посчитано ранее. Таким образом, находить эти длины k мы можем за каждую.
Итоговый алгоритм
Мы окончательно построили алгоритм, который не содержит явных сравнений строк
Итоговый алгоритм
Мы окончательно построили алгоритм, который не содержит явных сравнений строк
Приведем здесь итоговую схему алгоритма:
Считать значения префикс-функции prefix[i] будем по очереди: от i = 1 к i = n – 1 (prefix[0] = 0 – база).
Для подсчета текущего prefix[i] заводим переменную j, обозначающую длину текущего рассматриваемого образца. Изначально j = prefix[i – 1].
Проверяем образец длины j, для чего сравниваем символы string[i] и string[j]. Если они совпадают – то prefix[i] = j + 1 и переходим к индексу i + 1, иначе уменьшаем длину j, полагая ее равной prefix[j – 1], повторяем этот шаг алгоритма снова.
Если дошли до длины j = 0 и не нашли совпадения, то prefix[i] = 0, после чего переходим к следующему индексу (i + 1).
Реализация
В итоге алгоритм получился весьма простым и красивым:
Реализация
В итоге алгоритм получился весьма простым и красивым:
Полезные ссылки
- http://e-maxx.ru/algo/prefix_function
https://ru.wikipedia.org/wiki/Алгоритм_Кнута_—_Морриса_—_Пратта
http://habrahabr.ru/post/191454/
Полезные ссылки
- http://e-maxx.ru/algo/prefix_function
https://ru.wikipedia.org/wiki/Алгоритм_Кнута_—_Морриса_—_Пратта
http://habrahabr.ru/post/191454/