АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

237. Разнообразные строки

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Неизвестный

Будем называть разнообразностью строки количество символов, которые встречаются в ней равно один раз. Например, разнообразность строки "INFORMATICS" — 9, поскольку символы "A", "C", "F", "M", "N", "O", "R", "S" и "T" встречаются в ней ровно один раз.

Для заданной строки S найдите подстроку, которая имеет наибольшую разнообразность. Если таких подстрок несколько, то найдите ту, которая минимальна в лексикографическом порядке.

Строка A меньше строки B в лексикографическом порядке, если выполняется одно из условий:

1) A является началом B;

2) для некоторого числа i первые i символов строки A совпадают с первыми i символами строки B, а i + 1-й символ в строке A идёт в алфавите раньше i + 1-го символа в строке B.

Например, строка "SOL" меньше в лексикографическом порядке строк "SOLVE", "START", "TIME".

Формат входных данных

Входной файл содержит строку, состоящую только из заглавных букв латинского алфавита. Длина строки не превышает 2500 символов.

Формат выходных данных

Выведите в выходной файл подстроку исходной строки, имеющую максимальную разнообразность среди всех её подстрок. Если таких подстрок несколько, выведите минимальную в лексикографическом порядке.

Примеры входных и выходных файлов

stdin

stdout

ABBAC

BAC

OLYMP

OLYMP

AAA

A

AABBCC

AB

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований и сборов / Школьные олимпиады и курсы Вологодской области / ВсОШ, региональные этапы / Областная олимпиада школьников 2005-2006 /
236. Перепутанные диски 237. 238. Разрезание торта
 
время генерации 0.172 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.