시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 1 | 1 | 1 | 100.000% |
Рассмотрим строку 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 определяет ее странность.
Входной файл содержит строку s, состоящую из строчных букв латинского алфавита. Строка имеет длину от 1 до 200 000.
Выходной файл должен содержать одно целое число: странность заданной во входном файле строки.
번호 | 배점 | 제한 |
---|---|---|
1 | 29 | Строка s состоит только из букв «a» и «b». Длина строки s не превышает 50. |
2 | 12 | Длина строки s не превышает 50. |
3 | 25 | Длина строки s не превышает 1000. |
4 | 34 | Длина строки s не превышает 200 000. |
abba
7
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2016 3번