10320: CF EDU - Suffix Array - Step 5 - D. Borders
[Creator : ]
Description
String $t$ is a border of string $s$, if it is at the same time its suffix and prefix. For example, string abbabba has three borders: abba, a and an empty string.
Given a string $s$, calculate total number of borders of all its substrings.
Given a string $s$, calculate total number of borders of all its substrings.
Input
First string holds string $s\ (1≤|s|≤400,000)$. The string consists of small english characters.
Output
Output single integer – total number of borders for all substrings of $s$.
Sample 1 Input
ababb
Sample 1 Output
20
Sample 2 Input
hhya
Sample 2 Output
11
Sample 3 Input
aaazaaa
Sample 3 Output
50
a
1