19384번 - Circular Shift 출처다국어

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$.

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.