Ответы на вопрос:
Орел-зрение волк-обаняние летучие мыши-зрение дельфин-слух крот-осязание
Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. такой алгоритм будет работать o(|s|^2), что при ограничении |s| < = 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго. оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. их можно найти, а затем увеличивать длину до тех пор, пока это возможно. плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений. однако можно решить и за линейное время. например, существует алгоритм манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. а именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию. пример 1: "длинная" подстрока-палиндром: c bbaabbaabbc в которой известна подстрока-палиндром. тогда в строке есть симметричная подстрока-палиндром: cbbaa bbaabbc пример 2: "длинная" подстрока палиндром: bbaabbaabbaa зная, что в ней есть подстрока-палиндром bbaabbaabbaa, можно явные сравнения для подстроки с центром в bbaabb aabbaa начинать уже с bbaa bbaabbaa если не хочется писать самостоятельно, алгоритм манакера легко находится.
Реши свою проблему, спроси otvet5GPT
-
Быстро
Мгновенный ответ на твой вопрос -
Точно
Бот обладает знаниями во всех сферах -
Бесплатно
Задай вопрос и получи ответ бесплатно
Популярно: Информатика
-
1. могут ли углы α, β, γ быть углами одного треугольника....
diaweeti55119.10.2022 19:12 -
Дана программа: Python Паскаль C++ x = int(input()) y = int(input()) if x 100 and...
Ариана1611200109.08.2021 08:40 -
У исполнителя Альфа две команды, которым присвоены номера: 1. прибавь 1 2. умножь...
chudaevavera2923.05.2020 21:11 -
Напишите наибольшее число x, для которого истинно высказывание: (x 42) И НЕ (в числе...
pivovarchik07716.05.2022 03:01 -
Одномерный целочисленный массив из 15 элементов задан случайным образом на отрезке...
overlord73520.09.2020 03:52 -
Паскаль var m, k, i; integer; mas; array [1..10] of integer; begin mas[1]: =12;...
ром56922.04.2023 22:01 -
Program jmia; var a,b,c,d,e,f,h: real; bigin readln(a,b,c,d,e,f,); d: =(c-3*a*a)/18,5-(a*a+b*b)/b-a+(a+c*c)/3*c*c;...
Qudipue128.06.2020 10:30 -
Сообщение, записанное буквами из 128-символьного алфавита, содержит 40 символов....
Гогого1102.06.2020 09:59 -
Укажи порядок действий и вычисли35*(100: 25)+760=. 35-(48: 3*2)+19=...
Дахич124.03.2023 09:35 -
Іть будь ласка виконати завдання. випишіть з тексту слова , які не мають лексичного...
Сплткнлттаа29.05.2021 15:12
Есть вопросы?
-
Как otvet5GPT работает?
otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса. -
Сколько это стоит?
Проект находиться на стадии тестирования и все услуги бесплатны. -
Могу ли я использовать otvet5GPT в школе?
Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое! -
В чем отличия от ChatGPT?
otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.