Description
Input
一行，一个字符串S
Output
一行，一个整数，表示所求值
Sample Input
cacao
Sample Output
54
HINT
2<=N<=500000,S由小写英文字母组成
Solution
首先，对于原式中的len(Ti)+len(Tj)可以简单初始化得到，即1*(n-1)+...+i*(n-1)+...+n*(n-1)
此题的难点在于怎样求解2*LCP(Ti,Tj)的值
利用后缀数组的性质，可以看出，求LCP(Ti,Tj)即求min{h[rank[i]],...,h[rank[j]]}
对于此题，由于不用修改，我们不用考虑两两枚举i、j串再求最小值，只要考虑对于每个后缀i对其前后区间的最小值的贡献
设对于i点，它的最小值贡献区间为l[i],r[i]
则i对原始的贡献为 -(i-l[i]+1)*(r[i]-i+1)*h[i]
那么，就可以很容易的求解此题了