Codeforces Beta Round 92 (Div. 1 Only) |
---|
Закончено |
Дана строка s. Каждой паре чисел l и r, удовлетворяющих условию 1 ≤ l ≤ r ≤ |s|, соответствует подстрока строки s, начинающаяся в позиции l и заканчивающаяся в позиции r (включительно).
Определим функцию от двух строк F(x, y) следующим образом. Найдем список таких пар чисел, для которых соответствующие подстроки строки x равны строке y. Отсортируем этот список пар по возрастанию первого числа в паре. Значение функции F(x, y) равно количеству непустых непрерывных подпоследовательностей в списке.
Например: F(babbabbababbab, babb) = 6. Список пар:
(1, 4), (4, 7), (9, 12)
Его непрерывные подпоследовательности:
Для заданной строки s требуется подсчитать сумму F(s, x) для всех x, принадлежащих множеству всех подстрок строки s.
В единственной строке находится данная строка s, которая состоит только из маленьких латинских букв (1 ≤ |s| ≤ 105).
Выведите одно число — искомую сумму.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных целых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
aaaa
20
abcdef
21
abacabadabacaba
188
В первом примере значения функции при x равном «a», «aa», «aaa» и «aaaa» равны 10, 6, 3 и 1 соответственно.
Во втором примере для любого удовлетворяющего x значение функции равно 1.
Название |
---|