[NOIP2020] 字符串匹配

这真的是个蓝天吗？为什么它的前缀知识是个紫题....
算了，不管那么多了....
首先要有一个意识就是看到循环的时候,可以多向KMP的方向去靠近...（别问我为什么会知道..）
首先任何题都不是一下子想到某个算法,然后根据算法进行变形,靠近当前这个题。而应该是反过来的,我们先观察当前题有什么性质,根据它的性质或是我们需要解决的问题来确定算法之后解决。
首先看这个题\(F(s)\)的定义就很奇怪,奇数次的字符的数量。首先肯定是要将\((AB)^i\)和\(C\)是分开的。考虑某种情况下,我们找到了一个划分方式\((AB)^kC\),观察他有什么性质,容易发现k的奇偶性相同时,\(F(C)\)的值是一样的。因为当k每次增加2时,C所在的集合就会减少两个一样的区间。显然这两个一样的区间是对\(F(C)\)是不构成影响的。
那我们接下来的思路就有了,枚举循环节\(AB\),然后找出它最大的循环节。之后考虑\(F(C)\)即可。
循环节最大次数可以使用扩展KMP的z函数解决。F(C)可以预处理后缀的奇数次字符的数量解决。