409792: GYM103743 I Cutting Suffix

Given a string $$$S$$$ of length $$$n$$$ consisting of lowercase English characters. We denote $$$\text{Suffix}_i$$$ as the suffix of $$$S$$$ starting from the $$$i$$$-th character. We define $$$w_{i,j}$$$ as the length of the LCP of $$$\text{Suffix}_i$$$ and $$$\text{Suffix}_j$$$. LCP is the longest common prefix of two strings. For example, the LCP of $$$\texttt{abca}$$$ and $$$\texttt{abd}$$$ is $$$\texttt{ab}$$$.

You should divide the integers from $$$1$$$ to $$$n$$$ into two non-empty complementary sets $$$T_1, T_2$$$. We define the value of this partition as follows.

$$$$$$ \sum\limits_{i\in T_1}\sum\limits_{j\in T_2}w_{i,j} $$$$$$

Please find a partition to minimize the value.

The input contains a string $$$S$$$ of length $$$n$$$ ($$$2\leq n\leq 10^5$$$) in a single line, consisting of only lowercase English letters.

Output a single integer indicating the minimum value.

aa

1

ab

0