P7114 [NOIP2020] 字符串匹配

根据引用\[1\]，对于问题P7114 \[NOIP2020\] 字符串匹配，我们可以使用枚举的方法来确定AB的可能情况，并进一步确定C的可能情况。假设枚举的AB是前缀iii，那么C只可能是后缀i+1i+1i+1，以及后缀i+1i+1i+1去掉前面的若干AB后得到的后缀。我们可以预处理出每个前缀和后缀中出现奇数次字符的个数。根据观察，对于AB循环奇数次和偶数次来说，它们的C的上述值分别相同。因此，我们可以分别考虑AB循环奇数次和偶数次的情况，从前往后记录当前有多少个前缀的出现奇数次字符个数为i。在询问时，我们可以直接暴力询问前缀和，总的复杂度大约是O(26n)。如果使用树状数组，复杂度可以优化到O(nlog26)。

根据引用\[2\]，这个问题与周期串有关。朴素的KMP算法只能求出一个周期串的最小循环节，对于本题来说是不够的。我们需要知道对于一个AB来说，它最多能往后循环多少次。虽然可以使用二分法来解决，但是复杂度较高。

根据引用\[3\]，我们可以优化复杂度。由于postodd每次只变化1，我们可以记录从i变化到i+1或者i-1时，A串满足条件的个数的变化情况。对于奇数k，没有什么特殊的情况。对于偶数k，我们注意到C串的奇偶性与整串一致，因此可以直接使用整串的奇偶性即可。

综上所述，对于问题P7114 \[NOIP2020\] 字符串匹配，我们可以使用枚举的方法来确定AB的可能情况，并根据不同情况进行处理。可以使用树状数组来优化复杂度。
#### 引用[.reference_title]
- *1* *2* [【LuoguP7114】[NOIP2020] 字符串匹配 （扩展KMP算法）](https://blog.csdn.net/element_hero/article/details/113036427)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^koosearch_v1,239^v3^insert_chatgpt"}} ] [.reference_item]
- *3* [P7114 [NOIP2020] 字符串匹配](https://blog.csdn.net/beneath_haruhi/article/details/120634165)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^koosearch_v1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]