Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Странные строки

(Время: 1 сек. Память: 16 Мб Сложность: 52%)

Рассмотрим строку s, состоящую из строчных букв английского алфавита. Примером такой строки является, например, строка «abba».

Подстрокой строки s называется строка, составленная из одного или нескольких подряд идущих символов строки s. Обозначим как W(s) множество, состоящее из всех возможных подстрок строки s. При этом каждая подстрока входит в это множество не более одного раза, даже если она встречается в строке s несколько раз.

Например, W(«abba») = {«a», «b», «ab», «ba», «bb», «abb», «bba», «abba»}.

Подпоследовательностью строки s называется строка, которую можно получить из s удалением произвольного числа символов. Обозначим как Y(s) множество, состоящее из всех возможных подпоследовательностей строки s. Аналогично W(s), каждая подпоследовательность строки s включается в Y(s) ровно один раз, даже если она может быть получена несколькими способами удаления символов из строки s. Поскольку любая подстрока строки s является также ее подпоследовательностью, то множество Y(s) включает в себя W(s), но может содержать также и другие строки.

Например, Y(«abba») = W(«abba») ∪ {«aa», «aba»}. Знак ∪ обозначает объединение множеств.

Будем называть строку s странной, если для нее W(s) = Y(s). Так, строка «abba» не является странной, а, например, строка «abb» является, так как для нее W(«abb») = Y(«abb») = {«a», «b», «ab», «bb», «abb»}.

Будем называть странностью строки число ее различных странных подстрок. При вычислении странности подстрока считается один раз, даже если она встречается в строке s в качестве подстроки несколько раз. Так, для строки «abba» ее странность равна 7, любая ее подстрока, кроме всей строки, является странной.

Требуется написать программу, которая по заданной строке s определяет ее странность.

Входные данные

Входной файл INPUT.TXT содержит строку s, состоящую из строчных букв английского алфавита. Строка имеет длину от 1 до 200 000.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – странность заданной во входном файле строки.

Пример

INPUT.TXTOUTPUT.TXT
1abba7

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 A. Кольцевая линия
 B. Обычный мальчик
 C. Сыграем?
 D. Карточки
 E. Задача о назначениях
 F. Странные строки
 G. Количество учеников
 H. Муравей

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru