2021 EC-Final B. Beautiful String

题意：字符串s可以被分割为，其中，求整个字符串及其子串中有多少种字符串可以被这样分割

暴力做法：

先考虑暴力做法，记  表示  与  的最长公共前缀，那么类似于  可以得到转移方程 ，那么如果，那么就说明以  到  这一段的字符串在  之后又再次出现了，那么我们就可以得到上图中最前面的蓝色两部分，特别的，在上图中可以发现，之后出现的蓝色与橙色在之后重复出现，那么我们可以在  之后枚举（因为这样才找到了前面的两个蓝色部分），同样类似于之前的，如果有 （只要比蓝色部分多就行了） 那么蓝色和橙色部分也重复出现，但是绿色部分的长度至少为1，所以  从  开始枚举，同时 ，那么答案就要加上，本着交一发试试的心态，然后不出意外就TLE了

优化：

    可以发现，求  的过程其实没办法去优化的，同时  和  也没办法优化，因为我们总是需要枚举两个点去找到蓝色部分，那么我们可以尝试优化 ，对于  ， 若存在  对答案有贡献，那么 最少也是 （+1是因为要有一个绿色部分），也就是说，从 后面的第 个字符开始到整个字符串末尾都有可能对答案产生贡献。

    记表示从开始长度为  的贡献，若 ，那么根据上面的分析，，都需要加一，显然这个是个差分然后求前缀和的过程。那么现在就可以枚举和来计算贡献了，根据暴力解法，我们应该从开始长度为一直加到长度为这一段的值，也就是，那么这又是一个前缀和的过程，为了方便，我们可以把数组定义为差分数组，然后求两次前缀和就可以了

按理说应该是能过得，但是

那么就是一些小细节可以优化了，对于满足条件的贡献至多不超过原字符串长度的一半，因此第二维开到一半就够了。