Description
Input
一行,一个字符串S
Output
一行,一个整数,表示所求值
Sample Input
cacao
Sample Output
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]
那么,就可以很容易的求解此题了