НАДО 3 ВАРИАНТА ОТВЕТА НО У МЕНЯ ПОЛУЧАЕТСЯ ЧЕТЫРЕ
Программирование составных условий. Урок 2 Рассмотрите следующий код: if x > 2 and x 5): print("x попадает в отрезок (2; 7), y не попадает в отрезок (0; 5)") else: print("x не попадает в отрезок (2; 7), y попадает в отрезок (0; 5)") При каком значений x и y, результат кода будет: x попадает в отрезок (2; 7), y не попадает в отрезок (0; 5) Верных ответов: 3 x = 5; y = 0 x = 5; y = 4 x = 2; y = 16 x = 2; y = 5 x = 6; y = –10 x = 2; y = –2 x = 7; y = –2 x = 3; y = 3 Назад Проверить
149
175
Ответы на вопрос:
Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. такой алгоритм будет работать o(|s|^2), что при ограничении |s| < = 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго. оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. их можно найти, а затем увеличивать длину до тех пор, пока это возможно. плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений. однако можно решить и за линейное время. например, существует алгоритм манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. а именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию. пример 1: "длинная" подстрока-палиндром: c bbaabbaabbc в которой известна подстрока-палиндром. тогда в строке есть симметричная подстрока-палиндром: cbbaa bbaabbc пример 2: "длинная" подстрока палиндром: bbaabbaabbaa зная, что в ней есть подстрока-палиндром bbaabbaabbaa, можно явные сравнения для подстроки с центром в bbaabb aabbaa начинать уже с bbaa bbaabbaa если не хочется писать самостоятельно, алгоритм манакера легко находится.
Популярно: Информатика
-
271020001320.03.2022 07:38
-
ArtemPlayGames07.03.2021 23:27
-
ksutsydmi01.12.2022 17:13
-
nysha04611.11.2022 10:03
-
ivancerbadji06.08.2021 17:03
-
georgiy1997105.01.2022 23:30
-
Vishenka22008.06.2023 07:26
-
alpengold131014.04.2022 13:33
-
galina15704.08.2020 17:41
-
Kaaaaakkkktus22.10.2022 00:49