Yvision.kzYvision.kz
kk
Разное
Разное
399 773 постов41 подписчиков
Всяко-разно
1
00:00, 28 июля 2014

Нахождение самой длинной подстроки-палиндрома.

Задача:

Дана строка, требуется найти самую длинную подстроку, являющуюся палиндромом.

 

Решение:

Для поиска подстрок-палиндромов можно использовать следующий способ - начнем процесс поиска с центра строки. Для различных палиндромов центром может являться 1 либо 2 символа.

К примеру:

1) "роз узор" - центром является символ "у";

2) "барокко раб" - центром являются два символа "кк".

Для того, чтобы найти самый длинный палиндром с центром на произвольной позиции N, нужно произвести две проверки, для случаев 1 и 2.

1) Строка из одного символа сама по себе является палиндромом. Для того, чтобы выяснить, есть ли более длинный палиндром с центром в символе N, нужно начать сравнивать попарно символы на позициях [N-1, N+1], [N-2, N+2], и т. д. Продолжая сравнение таким образом до первой несовпадающей пары либо до границ строки, мы найдем самый длинный палиндром с центром в символе N.

2) Сравним символы N и N+1. Если они совпадают, у нас есть минимальный палиндром с центром в этих двух символах, размера 2.

Затем аналогично первому способу, начнем попарное сравнение [N-1, N+2], [N-2, N+3], и т. д.

Таким образом мы найдем самый длинный палиндром с центром в символах N и N+1

3) Проведя подобный поиск на каждой позиции исходной строки мы найдем самую длинную подстроку, являющуюся палиндромом.

Time complexity данного решения O(N^2). Статья о данном алгоритме на leetcode упоминает Алгоритм Манакера, который решает эту задачу за O(N). ИМХО, в контексте подготовки к интервью изучение данного алгоритма опционально.

Мое решение:
https://gist.github.com/codekrolik/80338e07438f2d2894dd

Тесты:
https://gist.github.com/codekrolik/24aaeb86085e4ae837c5

Пост на leetcode.

1
4809
0