【学习笔记】[JSOI2019]节日庆典

我觉得很厉害。因为这道字符串题目的分析非常自然而且并不复杂。

考虑枚举右端点到$r$时，维护可能成为答案的位置的集合。显然对于相邻两个元素$i,j$，我们有$\text{lcp(S[i:],S[j:])}>r-j$，否则可以删去$i,j$其中之一。画图不难发现我们只需要保证对于任意$k$，满足$\text{lcp(S[i:],S[k:])}>r-k$，也就是只用和第一个位置进行比对。注意$\text{lcp}$的长度是不随右端点$r$变化的，可以看成常数。

当然，上述分析并不能导向一个正确的解法。假设我们已经维护出来了上述集合，有一个非常套路的想法，假设已经检查完了$i$之前的所有位置，那么对于之后的一个位置$j$，假设$j-i<r-j$，那么不难发现$S[i:j)=S[j:2j-i)$，我们记这一段为$A$（更确切地说$A$是$S[i:r]$的周期），$2j-i$以后的为$B$，那么我们得到$A+A+B,A+B+A,B+A+A$三种方案。容易观察出中间那种肯定是不优的，也就是$j$一定不优。那么有$2j\ge r+i$，显然只有最多$\log$个需要检查，这道题就做完了。因为$\text{lcp}$已经匹配到了底所以用$z$函数辅助检查一下即可。

复杂度$O(n\log n)$。

代码咕了。其实是我不会打$z$函数

至于维护集合那个部分，可以自己编一个做法，事实上发现每次暴力重构就完了。