---
title: "Нахождение самой длинной подстроки-палиндрома."
description: "Задача: Дана строка, требуется найти самую длинную подстроку, являющуюся палиндромом. Решение: Для..."
author: "codekrolik"
published: "2014-07-28T00:00:55+00:00"
modified: "2014-07-28T00:01:35+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/nahozhdenie-samoy-dlinnoy-podstroki-palindroma-422995"
markdown_url: "https://yvision.kz/post/nahozhdenie-samoy-dlinnoy-podstroki-palindroma-422995/markdown"
site_name: "Yvision.kz"
---

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

> Задача: Дана строка, требуется найти самую длинную подстроку, являющуюся палиндромом. Решение: Для...

Задача:

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

 

Решение:

Для поиска подстрок-палиндромов можно использовать следующий способ - начнем процесс поиска с центра строки. Для различных палиндромов центром может являться 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/80338e07438f2d2894dd)

Тесты: [https://gist.github.com/codekrolik/24aaeb86085e4ae837c5](https://gist.github.com/codekrolik/24aaeb86085e4ae837c5)

[Пост на leetcode](http://www.programcreek.com/2013/12/LEETCODE-SOLUTION-OF-LONGEST-PALINDROMIC-SUBSTRING-JAVA/).

---

Source: [https://yvision.kz/post/nahozhdenie-samoy-dlinnoy-podstroki-palindroma-422995](https://yvision.kz/post/nahozhdenie-samoy-dlinnoy-podstroki-palindroma-422995)