Sum of Suffix Pair Differences

Given a string \(S\) of length \(n\), let \(T_i\) denote the suffix of \(S\) starting at the \(i\)-th character (1-indexed). You are required to compute:

\(\displaystyle \sum_{1\leq i<j\leq n}\Big(\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)\Big)\)

where:

• \(\operatorname{len}(a)\) denotes the length of string \(a\),
• \(\operatorname{lcp}(a,b)\) denotes the length of the longest common prefix of strings \(a\) and \(b\).

Note: The input string \(S\) does not come with an explicit limit. You may assume that \(n\) is small enough for a \(O(n^2)\) solution to pass.

inputFormat

The input consists of a single line containing the string \(S\). The string contains only printable characters and does not contain spaces.

outputFormat

Output a single integer: the result of the calculation.

sample

abac

28