409792: GYM103743 I Cutting Suffix

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Cutting Suffixtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output a single integer indicating the minimum value.

ExamplesInput
aa
Output
1
Input
ab
Output
0

加入题单

上一题 下一题 算法标签: