Петя и Вася любят играть в шпионов. А какие игры в шпионов обходятся без секретных шифровок! Вот и Вася недавно придумал новый
Вопрос пользователя
Петя и Вася любят играть в шпионов. А какие игры в шпионов обходятся без секретных шифровок! Вот и Вася недавно придумал новый способ шифрования своих сообщений. Информацию о том, как он шифрует, он оставил в секрете и сообщил Пете только способ расшифровки, чтобы тот всегда мог им воспользоваться.
Для расшифровки Пете необходимо всего лишь найти лексикографически максимальную подстроку в зашифрованном сообщении, которое ему передает Вася. Именно эта подстрока и будет исходным текстом. Поскольку Петя справляется с этим поиском не так быстро, как ему хотелось бы, он просит Вас написать программу, которая поможет ему в этом!
Ответ эксперта
Лексикографически максимальная подстрока будет начинаться с самого большого (в алфавитном порядке) символа исходной строки. Если одна строка является префиксом другой, то эта вторая строка будет лексикографически большей. Поэтому выгоднее выбирать максимальную подстроку начиная с самых левых символов. И при этом подстрока всегда должна заканчиваться последним символом исходной строки.
Поэтому можно перебрать левый символ подстроки и сравнивать полученную подстроку с текущим наилучшим вариантом. Если новая подстрока будет больше, то записать в текущий вариант ее.
Время работы программы составит O(N^2), где N – длина строки. Для N в пределах 1000 программа будет укладываться во временные ограничения.
