Prefix-Suffixes

Time limit1sMemory limit128 MB

Summary

Count proper borders summed over all substrings of a given lowercase word of length up to 10^5.

Level: Hard9 of 10
Topics: String matching, String, Prefix sum
Solved: No attempts yet

Problem

A prefix-suffix (a border) of a word $w$ is a word $v$ that is both a prefix (an initial fragment) and a suffix (a final fragment) of $w$ . A proper prefix-suffix of $w$ is any prefix-suffix that is non-empty and strictly shorter than $w$ . Let $\mathrm{PS}(w)$ denote the number of proper prefix-suffixes of $w$ . Let $w[i, j]$ denote the substring of $w$ that starts at position $i$ and ends at position $j$ ; positions are numbered from $1$ .

Given a word $w$ , compute the total number of proper prefix-suffixes over all substrings of $w$ , that is

$\sum_{1 \le i \le j \le |w|} \mathrm{PS}(w[i, j])$

Input

The first and only line of input contains the word $w$ . Its length satisfies $1 \le |w| \le 10^5$ , and it consists only of lowercase English letters.

Output

Print a single integer: the total number of proper prefix-suffixes over all substrings of $w$ .

Examples4

Example 1
Input
```
ababa
```
Expected output
```
7
```
Example 2
Input
```
aa
```
Expected output
```
1
```
Example 3
Input
```
aaaa
```
Expected output
```
10
```
Example 4
Input
```
abab
```
Expected output
```
3
```