Петя и Вася любят играть в шпионов. А какие игры в шпионов обходятся без секретных шифровок! Вот и Вася недавно придумал новый
108
485
Ответы на вопрос:
Лексикографически максимальная подстрока будет начинаться с самого большого (в алфавитном порядке) символа исходной строки. Если одна строка является префиксом другой, то эта вторая строка будет лексикографически большей. Поэтому выгоднее выбирать максимальную подстроку начиная с самых левых символов. И при этом подстрока всегда должна заканчиваться последним символом исходной строки.
Поэтому можно перебрать левый символ подстроки и сравнивать полученную подстроку с текущим наилучшим вариантом. Если новая подстрока будет больше, то записать в текущий вариант ее.
Время работы программы составит O(N^2), где N – длина строки. Для N в пределах 1000 программа будет укладываться во временные ограничения.
Поэтому можно перебрать левый символ подстроки и сравнивать полученную подстроку с текущим наилучшим вариантом. Если новая подстрока будет больше, то записать в текущий вариант ее.
Время работы программы составит O(N^2), где N – длина строки. Для N в пределах 1000 программа будет укладываться во временные ограничения.
Популярно: Другие предметы
-
kurtsmolovp00xqx12.06.2021 19:53
-
Иван5555118.12.2022 06:45
-
karinarigova211.10.2021 21:22
-
Lugazat22.01.2021 05:20
-
MariaWoLF200621.08.2022 11:17
-
nastysh2001112.02.2022 05:52
-
Егор400201.02.2021 10:41
-
annasevsehkocot04.06.2022 05:33
-
kdominsk7103.06.2022 07:08
-
Luska136730.03.2022 15:13