Самая длинная палиндромная подстрока за O(n)
Один из самых красивых алгоритмов в компьютерных науках, демонстрирующий, как можно получить огромное ускорение от медлительного O(n³) до молниеносно быстрого¹ O(n), просто взглянув на задачу с другой стороны. перспектива.
Задача состоит в том, чтобы найти самую длинную подстроку, которая является палиндромом (=читается одинаково справа налево и слева направо, например, гоночная машина). Например, самый длинный палиндром в Дроби никогда не бывают четными и нечетными — никогда не бывают четными и нечетными (регистр букв и пробелы игнорируются). Он имеет практическое применение в биохимии (GAATTC и CTTAAG называются палиндромными последовательностями²). Это типичное задание на собеседование³.
Самый простой подход (и одновременно самый медленный) состоит в том, чтобы перебрать все начала и длины, проверяя, является ли соответствующая подстрока палиндромом:
Псевдокод
loop over substring start:
__loop over substring length:
____loop over letters in substring
ясно указывает, что это метод O(n³) (где n — длина текста), который является быстро растущей функцией.
Если вместо того, чтобы перебирать начала, мы перебираем середины, мы сможем повторно использовать результаты предыдущих шагов.
Например, если мы знаем, что «канун» — это палиндром, нам потребуется еще одно сравнение, чтобы понять, что «уровень» — тоже палиндром. В первом методе нам пришлось бы заново запускать всю проверку с нуля.
loop over substring middle
__loop over substring length
Это O (n²). Но есть способы⁴, которые позволяют сделать это еще быстрее.
Одним из самых элегантных является алгоритм Манахера⁵. Он основан на методе O(n²), описанном выше, но введенная им эвристика сокращает временную сложность до O(n).
Когда палиндромы в тексте далеко друг от друга, тут и оптимизировать нечего. Это уже O(n). Проблема возникает, когда они пересекаются, в худшем случае это текст, состоящий из одной буквы.
Рассмотрим следующую ситуацию. Алгоритм нашел более короткий зеленый палиндром, более длинный синий палиндром и остановился на букве «i»:
Внимательный взгляд на изображение показывает, что на самом деле нет необходимости обрабатывать смещения правой половины синего палиндрома. По определению это зеркальное отражение левой половины, поэтому вся информация, которую мы собрали из левой половины, может быть отражена в правой половине «бесплатно»:
Однако это не единственный возможный случай перекрытия. На следующем изображении зеленый палиндром пересекает границу синего, поэтому его длина должна быть соответственно уменьшена:
Опять же, нет необходимости перепроверять длину отраженного палиндрома: буквы b и x должны быть разными, иначе синий палиндром станет длиннее.
Наконец, один палиндром может касаться другого изнутри. В этом случае нет гарантии, что отраженный палиндром не будет расти дальше, поэтому мы получаем только нижнюю границу его длины:
В идеале мы должны пропускать как нули, так и строго ненулевые значения (=все случаи, кроме последнего) при дальнейшей обработке (листинг 1 ниже). Но на практике (если можно говорить о практике в такой абстрактной задаче) разница между ≥ и = здесь настолько мала (всего одно лишнее сравнение), что имеет смысл все ненулевые значения рассматривать как ≥ ради кода краткость и удобочитаемость (листинг 2).
Одна из возможных реализаций этого алгоритма на Python:
Сначала он пытается найти соответствующее отражение, как описано выше. Затем, если необходимо, идет последовательный поиск: так же, как в алгоритме O(n²), но с учетом отраженного значения в качестве отправной точки. Наконец, если новый палиндром простирается дальше вправо, чем предыдущий крайний правый, он выбирается как новый крайний правый палиндром.
Эта функция находит только палиндромы нечетного размера. Чтобы это работало и с палиндромами четного размера, общий подход таков:
— чередовать произвольный символ между буквами исходного текста, например, ‘noon’ -> ‘|n|o|o|n|’,
— найти там палиндром нечетного размера, и, наконец,
— удалить эти символы из результата.
Символ «|» не обязательно должен отсутствовать в строке. Подойдет любой персонаж.
Немного запутанная версия (сложнее для понимания, чуть медленнее, но короче) выглядит так:
Как видно из кода, есть два вложенных цикла. Вот интуитивное понимание того, почему метод, тем не менее, O (n). На следующей диаграмме показан массив h.
Внешний цикл соответствует горизонтальному движению, внутренний цикл — вертикальному. Каждый шаг — одно сравнение. Сплошные линии — расчет шагов, штриховые — пропуск шагов.
Из диаграммы видно, что когда палиндромы не перекрываются, количество шагов вверх равно количеству пропущенных шагов по горизонтали. Для перекрывающихся палиндромов это несколько более надумано, но если вы посчитаете общее количество шагов вверх, оно снова совпадет с общим количеством пропущенных шагов по горизонтали. Таким образом, общее количество шагов ограничено 2n сравнениями. Это не n, потому что, в отличие от вертикальных шагов, чтобы понять, что горизонтальный шаг пропущен, вам все равно нужно проделать некоторую работу (хотя можно немного отрегулировать реализацию, чтобы пропустить группу из них за постоянное время). Таким образом, общее время равно O(n).
Алгоритм Манахера позволяет найти самый длинный палиндром в строке (на самом деле не просто самый длинный, а самый длинный палиндром для всех возможных центров) за линейное время, используя очень интуитивный подход, лучше всего описываемый визуально.
Рекомендации
- Сайт Big-O Cheat Sheet.
- Палиндромная последовательность, статья в Википедии.
- Самая длинная палиндромная подстрока, задача Leetcode.
- Самая длинная палиндромная подстрока, статья в Википедии.
- Манахер, Гленн (1975), Новый онлайн-алгоритм с линейным временем для нахождения наименьшего начального палиндрома строки, Journal of the ACM.
