시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 0 | 0 | 0 | 0.000% |
Vasya was at a meeting during his working day at Yandex. Suddenly he thought about a string $s$ consisting of lowercase English letters.
Then he decided that a string $t = t_{1} t_{2} \dots t_{m}$ ($m > 0$) is called a good string with respect to $s$ if $t$ is a substring of $s$ and the left circular shift $t' = t_{2} \dots t_{m} t_{1}$ of string $t$ is also a substring of $s$.
Vasya was going to calculate the number of different good strings $t$ with respect to the given string $s$...~but suddenly a colleague asked him a question, so he had to return back to reality. Find that number for Vasya while he is busy with the meeting.
The only input line contains a string $s$ consisting of $n$ ($1 \leq n \leq 300\,000$) lowercase English letters.
Output a single integer: the number of different good strings $t$ with respect to the given string $s$.
abaac
7
aaa
3
In the first sample case, the good strings are exactly the following strings: a
, b
, c
, aa
, ab
, ba
, aba
.
In the second sample case, the good strings are exactly the following strings: a
, aa
, aaa
.