Слово было зашифровано шифром цезаря. получилось мпцщьуъпо. расшифруйте его. используйте алфавит, состоящий из 33 букв. ответ запишите заглавными буквами.

139

303

Посмотреть ответы 2

Ответы на вопрос:

tagirova2

Информатика

4,5(70 оценок)

Уменя получилось слово велосипед

464679рли

Информатика

4,5(53 оценок)

Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. такой алгоритм будет работать o(|s|^2), что при ограничении |s| < = 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго. оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. их можно найти, а затем увеличивать длину до тех пор, пока это возможно. плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений. однако можно решить и за линейное время. например, существует алгоритм манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. а именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию. пример 1: "длинная" подстрока-палиндром: c bbaabbaabbc в которой известна подстрока-палиндром. тогда в строке есть симметричная подстрока-палиндром: cbbaa bbaabbc пример 2: "длинная" подстрока палиндром: bbaabbaabbaa зная, что в ней есть подстрока-палиндром bbaabbaabbaa, можно явные сравнения для подстроки с центром в bbaabb aabbaa начинать уже с bbaa bbaabbaa если не хочется писать самостоятельно, алгоритм манакера легко находится.