УДК 004.021

Новый алгоритм поиска самой длинной подстроки-палиндрома

Сивов Андрей Александрович – студент МИРЭА – Российского технологического университета.

Пыхтина Ирина Юрьевна – ассистент кафедры Телекоммуникаций Института радиоэлектроники и информатики МИРЭА – Российского технологического университета.

Аннотация: В статье исследуется проблема решения задачи поиска самой длинной подстроки палиндрома. Данная задача чаще всего рассматривается как подзадача поиска всех палиндромов в строке, при решении которой, поиск наибольшего палиндрома решается довольно просто.

Однако, вкладом авторов в исследования является создание нового алгоритма, специализированного именно под задачу поиска самой длинной подстроки палиндрома, а не общей задачи поиска всех палиндромов, в решении которой он эффективнее алгоритма Манакера минимум в два раза.

Ключевые слова: алгоритм, палиндром, поиск, сложность алгоритма, сравнение сложности.

Актуальность данного исследования заключается в поиске и предоставлении нового и эффективного алгоритма решения задачи поиска самой длинной подстроки палиндрома.

В данной статье будет кратко рассмотрен алгоритм Манакера [1], так как новый алгоритм имеет с ним отдаленное сходство, затем представлен новый алгоритм, а после приведены результаты сравнения сложности и скорости обоих алгоритмов [2].

На данный момент самым эффективным алгоритмом поиска всех подстрок-палиндромов, а следственно и самой длинной подстроки палиндрома [3] считается Алгоритм Манакера, который получая на вход произвольную строку возвращает массив чисел, индекс каждого из которых является центром палиндрома в строке (пускай и всего из одного символа в минимальном случае), а числовое значение говорит о длине палиндрома.

Из результатов этого алгоритма можно легко найти самый длинный палиндром в исходной строке. Достаточно найти индекс самого большого числа в полученном массиве.

Сложность такого алгоритма равна O(n) [4], что означает линейную зависимость времени алгоритма от длины строки [5]. Сам алгоритм на языке python представлен в листинге 1.

Листинг 1. Алгоритм Манакера.

def manacher_algorithm(s):

# Преобразуем строку s для учета четности длины палиндрома

modified_string = '#' + '#'.join(s) + '#'

n = len(modified_string)

# Массив для хранения длин палиндромных подстрок

palindrome_lengths = [0] * n

# Центр самого правого палиндрома

center = right_boundary = 0

for i in range(1, n - 1):

# Индекс зеркального символа относительно текущего центра

mirror = 2 * center - i

# Если текущий индекс меньше правой границы

if i < right_boundary:

palindrome_lengths[i] = min(right_boundary - i, palindrome_lengths[mirror])

# Расширяем палиндром вокруг текущего символа

try:

while modified_string[i + (1 + palindrome_lengths[i])] == modified_string[i - (1 + palindrome_lengths[i])]:

palindrome_lengths[i] += 1

except:

pass

# Обновляем центр и правую границу, если новый палиндром выходит за пределы текущего самого правого палиндрома

if i + palindrome_lengths[i] > right_boundary:

center = i

right_boundary = i + palindrome_lengths[i]

return palindrome_lengths

def max_palindrom(text):

palindrome_lengths=manacher_algorithm(text)

# Находим максимальную длину палиндрома в массиве длин палиндромов

max_length = max(palindrome_lengths)

# Находим индексы с максимальной длиной палиндрома

max_length_index = palindrome_lengths.index(max_length)

# Находим палиндромную подстроку

start_index = (max_length_index - max_length) // 2

return text[start_index:start_index + max_length]

В данном листинге функция manacher_algorithm(s) принимает строку и возвращает массив чисел, о котором говорилось выше, а функция max_palindrom(text) вызывает функцию manacher_algorithm(s) и с помощью полученного массива находит и возвращает палиндром максимальной длинны. А теперь будет представлен новый алгоритм, также на языке python в листинге 2.

Листинг 2. Новый алгоритм.

def new_algoritm(text):

text = '#' + text

n = len(text)

massiv0 = [1] * n

massiv1 = [1] * n

for i in range(2, n):

char0 = text[i] # текущий элемент

char1 = text[i - massiv1[i - 1]] # элемент для сравнения

if char0 == char1:

massiv1[i] = massiv1[i - 1] + 1 # если равны, увеличиваем длину найденного палиндрома

char1 = text[i - massiv0[i - 1] - 1] # новый элемент для сравнения

if char0 == char1:

massiv0[i] = massiv0[i - 1] + 2 # если равны, увеличиваем на 2

else:

massiv0[i] = massiv1[i] # в ином случае приравниваем в 0-ой массив элемент из 1-го.

# получаем индекс самого большого элемента в массиве

a = massiv0.index(max(massiv0))

return text[a - massiv0[a] + 1: a + 1]

Как видно из листингов, оба алгоритма имеют много сходств. Они оба проходят всю строку один раз, записывая длину найденных палиндромов в массив чисел.

Отличия нового алгоритма в том, что он записывает длину палиндрома в индекс его окончания, а не середину, и использует второй вспомогательный массив, где хранится информация о последовательности одинаковых символов. На каждой итерации новый алгоритм сравнивает текущий символ строки с двумя новыми символами для поиска палиндромов четной и нечетной длины.

Также стоит напомнить, что новый алгоритм хоть и хранит информацию о палиндромах, но не гарантирует нахождение информации обо всех палиндромах, зато в данном алгоритме внутри цикла for более нет цикла while, который присутствовал в алгоритме Манакера.

Актуальность нового алгоритма состоит в большей скорости выполнения, которая была протестирована на случайных символьных последовательностях разной длины. Результаты тестирования представлены в таблице 1.

Таблица 1. Скорость выполнения алгоритмов.

Как видно из результатов, новый алгоритм эффективнее алгоритма Манакера, и, хотя они оба имеют сложность O(n), средняя скорость выполнения у нового алгоритма всегда выше как минимум в два раза.

Список литературы

1. Алгоритм Манакера [Электронный ресурс]. – URL: https://ru.algorithmica.org/cs/string-searching/manacher/?ysclid=lvdqbfyumx708977527 (дата обращения: 20.04.2024).
2. Косолобов Д. А. Эффективные алгоритмы анализа закономерностей в строках— Уральский федеральный университет, 2015
3. Алгоритм поиска самой длинной подстроки-палиндрома // habr [Электронный ресурс]. – URL: https://habr.com/ru/articles/653617/ (дата обращения: 20.04.2024).
4. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: Построение и анализ [пер. с англ.] // — Издательский дом Вильямс, 2009.
5. Джон Клейнберг, Эва Тардос. Алгоритмы: разработка и применение, 2016.