MAXimal | |
добавлено: 23 Aug 2008 21:00 Содержание [скрыть] Нахождение всех подпалиндромовПостановка задачиДана строка длины . Требуется найти все такие пары , где , что подстрока является палиндромом (т.е. читается одинаково слева направо и справа налево). Уточнение постановкиПонятно, что в худшем случае таких подстрок-палиндромов может быть , и на первый взгляд кажется, что алгоритма с линейной асимптотикой существовать не может. Однако информацию о найденных палиндромах можно возвращать более компактно: для каждой позиции найдём значения и , обозначающие количество палиндромов соответственно нечётной и чётной длины с центром в позиции . Например, в строке есть три палиндрома нечётной длины с центром в символе , т.е. значение : А в строке есть два палиндрома чётной длины с центром в символе , т.е. значение : Т.е. идея — в том, что если есть подпалиндром длины с центром в какой-то позиции , то есть также подпалиндромы длины , , и т.д. с центрами в . Поэтому двух таких массивов и достаточно для хранения информации обо всех подпалиндромах этой строки. Достаточно неожиданным фактом является то, что существует довольно простой алгоритм, который вычисляет эти "массивы палиндромностей" и за линейное время. Этот алгоритм и описывается в данной статье. РешениеВообще говоря, данная задача имеет несколько известных решений: с помощью техники хэширования её можно решить за , а с помощью суффиксных деревьев и быстрого алгоритма LCA эту задачу можно решить за . Однако описываемый в данной статье метод значительно проще, и обладает меньшими скрытыми константами в асимптотике времени и памяти. Этот алгоритм был открыт Гленном Манакером (Glenn Manacher) в 1975 г. Тривиальный алгоритмВо избежание неоднозначностей при дальнейшем описании условимся, что же такое есть "тривиальный алгоритм". Это алгоритм, который для поиска ответа в позиции раз за разом пробует увеличить ответ на единицу, каждый раз сравнивая пару соответствующих символов. Такой алгоритм слишком медленен, весь ответ он может посчитать лишь за время . Приведём для наглядности его реализацию: vector<int> d1 (n), d2 (n); for (int i=0; i<n; ++i) { d1[i] = 1; while (i-d1[i] >= 0 && i+d1[i] < n && s[i-d1[i]] == s[i+d1[i]]) ++d1[i]; d2[i] = 0; while (i-d2[i]-1 >= 0 && i+d2[i] < n && s[i-d2[i]-1] == s[i+d2[i]]) ++d2[i]; } Алгоритм МанакераНаучимся сначала находить все подпалиндромы нечётной длины, т.е. вычислять массив ; решение для палиндромов чётной длины (т.е. нахождение массива ) получится небольшой модификацией этого. Для быстрого вычисления будем поддерживать границы самого правого из обнаруженных подпалиндрома (т.е. подпалиндрома с наибольшим значением ). Изначально можно положить . Итак, пусть мы хотим вычислить значение для очередного , при этом все предыдущие значения уже подсчитаны.
В завершение описания алгоритма сталось только напомнить, что надо не забывать обновлять значения после вычисления очередного значения . Также повторимся, что выше мы описали рассуждения для вычисления массива нечётных палиндромов ; для массива чётных палиндромов все рассуждения аналогичны. Оценка асимптотики алгоритма МанакераНа первый взгляд не очевидно, что данный алгоритм имеет линейную асимптотику: при вычислении ответа для определённой позиции в нём нередко запускается тривиальный алгоритм поиска палиндромов. Однако более внимательный анализ показывает, что алгоритм всё же линеен. (Стоит сослаться на известный алгоритм построения Z-функции строки, который внутренне сильно напоминает данный алгоритм, и работает также за линейное время.) В самом деле, легко проследить по алгоритму, что каждая итерация, производимая тривиальным поиском, приводит к увеличению на один границы . При этом уменьшений по ходу алгоритма происходить не может. Следовательно, тривиальный алгоритм в сумме совершит лишь действий. Учитывая, что, кроме тривиальных поисков, все остальные части алгоритма Манакера очевидно работают за линейное время, мы и получаем итоговую асимптотику: . Реализация алгоритма МанакераДля случая подпалиндромов нечётной длины, т.е. для вычисления массива , получаем такой код: vector<int> d1 (n); int l=0, r=-1; for (int i=0; i<n; ++i) { int k = i>r ? 1 : min (d1[l+r-i], r-i+1); while (i+k < n && i-k >= 0 && s[i+k] == s[i-k]) ++k; d1[i] = k; if (i+k-1 > r) l = i-k+1, r = i+k-1; } Для подпалиндромов чётной длины, т.е. для вычисления массива , лишь немного меняются арифметические выражения: vector<int> d2 (n); l=0, r=-1; for (int i=0; i<n; ++i) { int k = i>r ? 0 : min (d2[l+r-i+1], r-i+1); while (i+k < n && i-k-1 >= 0 && s[i+k] == s[i-k-1]) ++k; d2[i] = k; if (i+k-1 > r) l = i-k, r = i+k-1; } Задачи в online judgesСписок задач, которые можно сдать с использованием этого алгоритма:
|