Как найти палиндром в строке с

Как найти самую короткую лексикографически минимальную палиндромную подстроку в строке?

Подскажите, пожалуйста, алгоритм нахождения самой короткой лексикографически минимальной палиндромной подстроки в строке. Например, в случае строки «aboobaa» программа должна вывести «aa», а не «oo», так как «aa» лексикографически меньше чем «oo» («a» идет раньше в таблице ASCII чем «o»).

По условию задачи пустая строка и строка из одного символа не являются палиндромами.

Желательно, язык C++, так как нужно уложиться по времени в секунду. А длина строки достигает 200 000 символов.
Но можно и python.

Отслеживать
2,776 2 2 золотых знака 10 10 серебряных знаков 37 37 бронзовых знаков
задан 9 сен 2023 в 11:39
minipekka123123 minipekka123123
Пустая строка — палиндромная. Любая строка из одного символа — палиндромная.
9 сен 2023 в 12:08
Подумайте над вопросом: почему не надо искать кратчайшую палиндромную из десяти символов?
9 сен 2023 в 12:13

не знаю. пустая строка не является палиндромной в условиях задачи, и ответом задачи может быть минимум две буквы, например «aa».

9 сен 2023 в 12:27
Имеет смысл написать об этом в вопросе. Что ещё из условий опущено?
9 сен 2023 в 12:31
9 сен 2023 в 12:56

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

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

Палиндромы могут быть четной длины и нечетной длины, палиндром четной длины больше двух содержит в себе палиндром длиной в два символа vbbv, палиндром нечетной длины больше трех символов, содержит в себе палиндром длиной в три символа sdfds? значит задача сводится к поиску двух и трех символьных палиндромов т.е. самых коротких.

import random # Генерируем строку s для примера c = 'abcdefghijklmnopqrstuwvyxz' s = ''.join([c[random.randint(0, 25)] for _ in range(200_000)]) # s - строка из 200_000 символов из c # pol - список найденных палиндромов # Если первый и второй символ равны инициализируем список pol = [s[0] + s[1]] if s[0] == s[1] else [] pol1 = [] for i, j, k in zip(s, s[1:], s[2:]): # Если первый и третий символы равны "fdf" заносим в список if i == k: pol1.append(i + j + k) # Если второй и третий символы равны "fdd" заносим в список "dd" if j == k: pol.append(j + k) if pol: print(min(pol)) elif pol1: print(min(pol1)) else: print("Нет палиндромов") 

Задача с собеседования: как найти палиндром

Продолжаем разбирать задачки с сайта Leetcode. В прошлый раз было про массив и сумму чисел, теперь тоже необычное.

Условия

В переменной X лежит какое-то целое число

Задача — проверить, является ли это число палиндромом.

Задача со звёздочкой — проверить на наличие палиндрома, не используя строки.

Палиндром — это когда строка или число одинаково читается в прямом и обратном направлении:

121 — это палиндром.

А роза упала на лапу Азора — тоже палиндром (если не считать заглавных букв).

12321 — и это палиндром.

Решение, где используем строки

Самый простой способ проверить, число в переменной палиндром или нет, — преобразовать его в строку, выставить знаки задом наперёд и сравнить с оригиналом. Этим мы сразу решаем проблему отрицательных чисел, когда «−121»превращается в «121−» и сразу становится ясно, что это не палиндром.

Сначала решим это на Python. Тут вообще суть в одной строке:

X = 121 if str(X) == str(X)[::-1]: print("Это палиндром") else: print("Это не палиндром")

Здесь мы использовали трюк с переворачиванием строки без её изменения — применили конструкцию [::-1]. Работает это так:

• Первым параметром указывают начало, откуда начинать обработку строки. Раз ничего не указано, то начинаем с первого символа.
• Второй параметр — на каком по счёту символе надо остановиться. Здесь тоже ничего нет, поэтому алгоритм пройдёт до конца строки.
• Последний параметр — шаг и направление обработки. У нас указана минус единица, значит, алгоритм обработает строку справа налево, на каждом шаге считывая по символу.
• В итоге этот код вернёт нам строку, собранную в обратном порядке, при этом с оригинальной строкой ничего не случится — она останется неизменной.

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

Теперь решим это же, но на JavaScript:

var X = 121; if (X.toString().split("").reverse().join("") == X.toString()) < console.log("Это палиндром") >else

Здесь мы использовали другой метод пересборки:

1. X.toString() — переводит число в строку.
2. split(«») — разбивает строку на массив из символов. В кавычках принцип разделения — если бы там была точка, то разделили бы на местах точек. А так как там пустота, то делится вообще по каждому из символов.
3. reverse() — меняет элементы в массиве в обратном порядке.
4. join(«») — добавляет результат к пустой строке, чтобы на выходе получить строку в обратном порядке.

Решение без строк

Тем, кто справился с первой частью, предлагают задачу со звёздочкой — сделать то же самое, но не используя строки, а работая только с числами. Попробуем и мы.

Сделаем в JavaScript функцию, которая будет возвращать true, если в переменной лежит палиндром, и false — если нет. Всё остальное будем писать внутри этой функции:

Теперь обработаем три стандартные ситуации:

1. Если в переменной лежит ноль, то это палиндром.
2. Если переменная меньше ноля, то это не палиндром.
3. Если переменная делится на 10 без остатка — это тоже не палиндром.

Запишем это на JavaScript:

function palindrome(x) < // если перед нами ноль — это палиндром if(x == 0) < return true; >// если число меньше нуля или делится на 10 без остатка — это не палиндром if(x < 0 || x%10 == 0)< return false; >>

Чтобы проверить, является ли число палиндромом или нет, можно сделать так: отрезаем от числа цифры справа по одной, добавляем их в начало нового числа и постоянно сравниваем новое и старое значение. Если они станут равны — перед нами палиндром. Читайте комментарии, чтобы вникнуть в то, что происходит в коде:

function palindrome(x) < // если перед нами ноль — это палиндром if(x == 0) < return true; >// если число меньше нуля или делится на 10 без остатка — это не палиндром if(x < 0 || x%10 == 0)< return false; >// сюда будем собирать число в обратном порядке temp = 0; // а тут будем хранить промежуточные значения икса preX = x; // пока не дойдём до середины числа — повторяем цикл while (x > temp) < // берём самую правую цифру в числе — это остаток от деления на 10 pop = x%10; // запоминаем старое значение переменной X preX = x; // и отрезаем от переменной последнюю цифру — делаем это через целую часть деления на 10 x /= 10; // добавляем отрезанную цифру к обратной переменной temp = temp*10 + pop; >// если обратная переменная совпала с оставшейся половиной исходной переменной — это палиндром // мы добавляем сравнение с предыдущей версией исходной половины (которая на 1 цифру больше) на тот случай, если исходное число состояло из нечётного количества символов и его нельзя было бы разбить строго пополам if(x == temp || preX == temp) return true; // else return false; >;

Для запуска кода просто вызываем функцию и передаём её нашу переменную:

// запускаем код
var X = 121;
console.log(palindrome(X));

Чтобы попрактиковаться, попробуйте сделать такое же, но на Python и не подглядывая в наш код.

Получите ИТ-профессию

В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.

Палиндром. Проверить, является ли слово, строка, число палиндромом на C++

В данной статье решается задача по реализации программы(кода) на C++ для проверки, является ли слово, строка или число палиндромом. Программа должна просить ввести строку( не важно слово это или число), проверять, является ли она палиндромом и возвращать результат.

Что такое палиндром?

Палиндром — это строка(или число), которое можно прочитать одинаково справа налево, либо слева направо.

К примеру, слово «кот» не является палиндромом, а слово «потоп» является палиндромом. Также и с числами: число 12314 — не палиндром, число 345543 — палиндром.

Поняв это, можно начинать реализовывать алгоритм программы.

Функция проверки слова на палидром в C++

Для определения, является ли строка палиндромом, напишем функцию, которая примет на вход строку(объект string), а на выходе вернет логическое значение(тип данных bool). Строка будет содержать слово или число, которое функция проверит на палиндромность. Выходное значение true будет соответствовать тому, что строка является палиндромом, false будет соответствовать тому, что строка НЕ является палиндромом.

Обратите внимание, что строка — это, по сути своей, обычный одномерый массив.

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

Реализуем это в виде кода.

Для начала необходимо определить, сколько символов в строке, для этого воспользуемся методом length().

int len = word.length();

word — это строка, которую приняла функция. Теперь переменная len хранит значение длины строки.

После чего создадим цикл от 0 до len/2 и будем сравнивать элементы.

for(int i = 0; i < len/2; ++i) < if(word[i] != word[len-i-1]) < return false; >>

Обратите внимание, в цикле есть условие. Если i-ый элемент не равен элементу len-i-1, то сразу возвращается false(То есть не палиндром).

Массивы в C++ нумеруются от 0, поэтому чтобы получить первый элемент строки, нам нужно достать 0-ой элемент из массива, а чтобы последний, то нам нужно достать len-1.

Как работает функция проверки на палиндром

Допустим, у нас слово «мотор», то len будет равна 5.

|м о т о р|

|0 1 2 3 4|

Чтобы получить значение последней буквы, необходимо обратиться к массиву строки с индексом len-1 = 4. А чтобы получить значение первой буквы — обращаемся к элементу 0.

Для наглядности немного визуализируем работу функции:

1.Получаем слово «комок».

3. комок

Сравниваем к и к, они равны, идем дальше.

4. комок

Сравниваем о и о, они равны. Далее цикл останавливается, т.к. запущен до len/2, а это 5/2 = 2. В C++ результатом целочисленного деления является целое число с отброшенной дробной частью.

5. В конце функции возвращается true. Что означает, что слово палиндром.

Если бы во время сравнений букв получилось так, что они НЕ равны, то функция сразу бы завершила работу и вернула значение false. Что означает, что слово не палиндром.

Используем нашу функцию проверки на палиндром в программе на C++

Теперь нашу функцию можно вставить в программу на C++ и использовать. Напишем небольшое приложение, которое просит пользователя ввести слово(или число) в консоль, а после этого сообщает ему, является ли введенное слово палиндромом.

Код нашего приложения — это и есть решение задачи «Проверить, является ли слово палиндромом на C++»

Код программы на C++:

#include #include using namespace std; bool check_polindrom(string word) < int len = word.length(); for(int i = 0; i < len/2; ++i) < if(word[i] != word[len-i-1]) < return false; >> return true; > int main() < string str; cout > str; if(check_polindrom(str)) < cout else < cout return 0; >

Теперь компилируем, запускаем и проверяем.

Проверим словом «palindrom»

palindrom — не палиндром

Программа сообщила, что слово не является палиндромом, а это так и есть на самом деле.

Проверим выдуманным словом палиндромом «potomotop»

Программа сообщила, что введенное слово палиндром. Всё верно.

Вот таким алгоритмом можно проверить является ли слово палиндромом. Данная программа работает не только со словами, но и с числами. Не требует сторонних библиотек. Решения других задач по программированию на языке C++ можно найти в этом разделе.

Для вас это может быть интересно:

Раздел: Алгоритмы Программирование Метки: C++, string, алгоритм, код, палиндром, функция

Палиндром. Проверить, является ли слово, строка, число палиндромом на C++ : 3 комментария

1. Роман 25.10.2016 Оооооочень понятно и доходчиво, спасибо большое!

Палиндромы

Палиндром — это фраза, которая читается одинаково слева направо и справа налево. Например:

• «was it a car or a cat I saw?»
• «а роза упала на лапу Азора»
• «abacaba» (палиндром нечётной длины)
• «abba» (палиндром чётной длины)

Для простоты, мы будем рассматривать только последовательности из строчных латинских букв.

Палиндромы — не самые часто встречающиеся в реальной жизни объекты, однако задачи на палиндромы любят давать на соревнованиях по спортивному программированию. В этой статье мы опишем эффективные способы их представления.

Алгоритм Манакера

Пусть есть строка \(s\) и мы хотим найти в ней все подпалиндромы.

Мы сразу сталкиваемся с очевидной трудностью: их в строке может быть \(O(n^2)\) , что можно видеть на примере строки \(s = aa \ldots a\) . Поэтому будем использовать следующий формат: для каждой позиции \(s_i\) найдём наибольший палиндром, центр которого совпадает с \(s_i\) (чётные и нечётные палиндромы будем рассматривать отдельно). Половину его длины, округлённую вниз, будем называть радиусом.

Наивное решение — перебрать \(s_i\) , а для него вторым циклом находить наибольшую искомую длину:

 vectorint> pal_array(string s)  int n = s.size(); // окружим строку спецсимволами, чтобы не рассматривать выход за границы s = "#" + s + "$"; // в этом массиве будем хранить расстояние от центра до границы палиндрома vectorint> t(n, 0); for(int i = 1; i  n; i++) while (s[i - t[i - 1]] == s[i + t[i - 1]]) r[i-1]++; return r; >

Тот же пример \(s = aa\dots a\) показывает, что данная реализация работает за \(O(n^2)\) .

Для оптимизации применим идею, знакомую из алгоритма z-функции: при инициализации \(t_i\) будем пользоваться уже посчитанными \(t\) . А именно, будем поддерживать \((l, r)\) — интервал, соответствующий самому правому из найденных подпалиндромов. Тогда мы можем сказать, что часть наибольшего палиндрома с центром в \(s_i\) , которая лежит внутри \(s_\) , имеет радиус хотя бы \(\min(r-i, \; t_)\) . Первая величина равна длине, дальше которой произошел бы выход за пределы \(s_\) , а вторая — значению радиуса в позиции, зеркальной относительно центра палиндрома \(s_\) .

  vectorint> manacher_odd(string s)  int n = (int) s.size(); vectorint> d(n, 1); int l = 0, r = 0; for (int i = 1; i  n; i++)  if (i  r) d[i] = min(r - i + 1, d[l + r - i]); while (i - d[i] >= 0 && i + d[i]  n && s[i - d[i]] == s[i + d[i]]) d[i]++; if (i + d[i] - 1 > r) l = i - d[i] + 1, r = i + d[i] - 1; > return d; >

Так же, как и z-функция, алгоритм работает за линейное время: цикл while запускается только когда \(t_i = r — i\) (иначе палиндром уже во что-то упёрся), и каждая его итерация сдвигает увеличивает \(r\) на единицу. Так как \(r \leq n\) , получаем, что суммарно эти циклы сделают \(O(n)\) итераций.

Для случая чётных палиндромов меняется только индексация:

 vectorint> manacher_even(string s)  int n = (int) s.size(); vectorint> d(n, 0); int l = -1, r = -1; for (int i = 0; i  n - 1; i++)  if (i  r) d[i] = min(r - i, d[l + r - i - 1]); while (i - d[i] >= 0 && i + d[i] + 1  n && s[i - d[i]] == s[i + d[i] + 1]) d[i]++; if (i + d[i] > r) l = i - d[i] + 1, r = i + d[i]; > return d; >

Также можно было не писать отдельно две реализации, а воспользоваться следующим трюком — сделать замену:

\[ S = s_1 s_2 \dots s_n \to S^* = s_1 \# s_2 \# \dots \# s_n \]

Теперь нечётные палиндромы с центром в \(s_i\) соответствуют нечётным палиндромам исходной строки, а нечётные палиндромы с центром в \(\#\) — чётным.

Дерево палиндромов

Дерево палиндромов (англ. palindromic tree, EERTREE) — структура данных, использующая другой, более мощный формат хранения информации обо всех подпалиндромах, чем размеры \(n\) палиндромов. Она была предложена Михаилом Рубинчиком на летних петрозаводских сборах в 2014-м году.

Лемма. В строке есть не более \(n\) различных подпалиндромов.

Доказательство. Пусть мы дописываем к строке по одному символу и в данный момент, записав \(r\) символов, имеем наибольший суффикс-палиндром \(s_\) . Пусть у него, в свою очередь, есть суффикс-палиндром \(s_ = t\) . Тогда он также имеет более раннее вхождение в строку как \(s_ = t\) . Таким образом, с каждым новым символом у строки появляется не более одного нового палиндрома, и если таковой есть, то это всегда наибольший суффикс-палиндром.

Этот факт позволяет сопоставить всем палиндромам строки сопоставить следующую структуру: возьмём от каждого палиндрома его правую половину (например, \(caba\) для \(abacaba\) или \(ba\) для \(abba\) ; будем рассматривать пока что только чётные палиндромы) и добавим все эти половины в префиксное дерево — получившуюся структуру и будем называть деревом палиндромов.

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

Построение за линейное время

Будем поддерживать наибольший суффикс-палиндром. Когда мы будем дописывать очередной символ \(c\) , нужно найти наибольший суффикс этого палиндрома, который может быть дополнен символом \(c\) — это и будет новый наидлиннейший суффикс-палиндром.

Для этого поступим аналогично алгоритму Ахо-Корасик: будем поддерживать для каждого палиндрома суффиксную ссылку \(l(v)\) , ведущую из \(v\) в её наибольший суффикс-палиндром. При добавлении очередного символа, будем подниматься по суффиксным ссылкам, пока не найдём вершину, из которой можно совершить нужный переход.

Если в подходящей вершине этого перехода не существовало, то нужно создать новую вершину, и для неё тоже понадобится своя суффиксная ссылка. Чтобы найти её, будем продолжать подниматься по суффиксным ссылкам предыдущего суффикс-палиндрома, пока не найдём второе такое место, которое мы можем дополнить символом \(c\) .

 const int maxn = 1e5, k = 26; int s[maxn], len[maxn], link[maxn], to[maxn][k]; int n, last, sz; void init()  s[n++] = -1; link[0] = 1; len[1] = -1; sz = 2; > int get_link(int v)  while (s[n-len[v]-2] != s[n-1]) v = link[v]; return v; > void add_char(int c)  s[n++] = c; last = get_link(last); if (!to[last][c])  len[sz] = len[last] + 2; link[sz] = to[get_link(link[last])][c]; to[last][c] = sz++; > last = to[last][c]; >

Здесь мы использовали обычный массив для хранения переходов. Как и для любых префиксных деревьев, вместо него можно использовтать бинарное дерево поиска, хэш-таблицу, односвязный список и другие структуры, позволяющие обменять время на память, немного изменив асимптотику.

Асимптотика

Покажем линейность алгоритма. Рассмотрим длину наибольшего суффикс-палиндрома строки. Каждый новый символ увеличивает её не более, чем на 2. При этом каждый переход по суффиксной ссылке уменьшает её, поэтому нахождение первого суффикс-палиндрома амортизировано работает за линейное время.

Аналогичными рассуждениями о длине второго суффикс-палиндрома (его длина увеличивается тоже не более, чем на 2) получаем, что пересчёт суффиксных ссылок при создании новых вершин тоже суммарно работает за линейное время.