NOIp 2020 T2 字符串匹配 题解

· · 题解

闲话：NOIp 前一天，我刚刚奶了一口：“往年 NOIp 没考过 KMP，不 用 复 习 了。”

然后。T2 开幕雷击 虽然是扩展 KMP 我也不会。

回到正轨。

做法一

按照题意枚举 A,\,B,\,C，再判断是否符合条件。其中，A 一定是 S 的一个前缀，C 一定是 S 的一个后缀，B 是中间的一个子串。枚举复杂度 O(n^3)，判断复杂度 O(n)，整体复杂度 O(n^4)，预计得分 16pts。

实际上稍加优化就能达到 O(n^3) 复杂度，方法不少，预计得分 32pts。

做法二

预处理 S 中所有前缀字符串和后缀字符串出现奇数个字符的个数。

枚举 (AB) 的总长度，然后枚举 (AB) 重复的次数 i，直到 AB 不再重复或者已经达到 S 的总长度。由于 S=(AB)^iC，所有剩下的部分就是 C。

讨论满足条件的 A 的个数，由于预处理过，每次判断复杂度为 O(1)。

总复杂度 O(n^2+|S|)，预计得分 48pts。

特殊性质一

枚举 $C$ 的长度，假设剩下的长度为 $l$，则 $(AB)$ 的长度一定是 $l$ 的一个非 $1$ 因数。 - 如果 $C$ 的长度为奇数，那么 $A$ 的长度随意。 - 如果 $C$ 的长度为偶数，那么 $A$ 的长度也为偶数。 每次 $O(1)$ 计算，总复杂度 $O(n)$。结合 $O(n^2)$ 做法，期望得分 $56pts$。 #### 特殊性质二 $S$ 中只包含两种字符。 结合特殊性质，出现奇数次字符的个数只可能是 $0,\,1$ 或 $2$。枚举 $(AB)$ 的总长度，可以用字符串哈希快速求出 $(AB)$ 最多重复多少次。 枚举 $(AB)$ 重复的次数 $i$ 相当于调和级数求和，最终复杂度 $O(n \log n)$。结合做法二和特殊性质一，期望得分 $68pts$。 ### 做法三 特殊性质二统计有多少 $A$ 符合条件只需考虑 $0,\,1$ 和 $2$ 三种奇数个字符个数的情况。我们发现，需要考虑的最多奇数个字符的个数是 $26$ 个。用树状数组维护即可。 时间复杂度 $O(n \log n \log 26)$，期望得分 $84pts$。 ### 正解 继续分析发现，对于固定的 $(AB)$，根据重复次数的奇偶性，其对应的 $C$ 中出现奇数次的字符个数只有两种可能。 直接统计每种可能对答案的贡献即可。复杂度 $O(n \log 26)$，期望得分 $100pts$。