- 题意
给出一个长度为(n(leqslant 50000))的字符串，求形如(mathrm{UVU})形式的字串，其中(mathrm{V})的长度给定。 - 题解
枚举(mathrm{U})的长度(L)，考虑第一个(mathrm{U})的出现位置，显然每一个这样的(mathrm{U})都必然覆盖且仅覆盖一个(kL,k in N)的位置，那么我们考虑在这个位置统计到它，对于一个(kL)的位置，它对答案的贡献是(max(min(L, lcp_{pre}(i, i + L + h)) + min(L, lcp_{suf}(i, i + L + h)))，(lcp_{pre}, lcp_{suf})分别表示前缀和后缀的最长公共子串。
根据调和级数，复杂度为(O(nlog n)) - code