--->
2 задач
<---
Источники
Дана строка S. Назовем ее подстрокой строку с i-го по j-й символ (i ≤ j). Ваша задача — посчитать количество различных подстрок данной строки.
Во входном файле находится одна строка S, состоящая не более, чем из 200000 символов. Все символы в строке — маленькие латинские буквы.
В выходной файл выведите единственное число — количество различных подстрок заданной строки. Гарантируется, что в данных тестах ответ не более 1018.
aaba
8
Скажем, что последовательность строк t 1 , ..., t k является путешествием длины k , если для всех i > 1 t i является подстрокой t i - 1 строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.
Определим путешествие по строке s как путешествие t 1 , ..., t k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u 1 , ..., u k + 1 , такие, что s = u 1 t 1 u 2 t 2 ... u k t k u k + 1 . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.
Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .
Во второй строке содержится строка s , состоящая из n строчных английских букв.
Выведите одно число — наибольшую длину путешествия по строке s .
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .
Во втором примере подходящим вариантом будет { bb , b } .
7 abcdbcc
3
4 bbcb
2