【CF961F】k-substrings 题意 给定一个长度为 n 的字符串 S 我们设 S 的 k-子串 是 S[k … n - k + 1] ，设字符串 t 是字符串 T 的 奇正确前后缀 当且仅当满足以下条件： t 长度为奇数 |t| < |T| t 是 T 的 border （既是前缀又是后缀） 对于 k = 1 … n / 2 上取整，求 S 的 k-子串 的最长 奇正确前后缀 长度。无解输出 -1 2 ≤ n ≤ 1,000,000 官方题解 枚举某个前缀（指题目要求的相同前后缀中的前缀）的中心位置 i ，那么对应后缀的中心位置已经确定了（ n - i + 1 ），可以二分答案求出对于每个中心位置 i 最大的符合要求的相同前后缀（设长度为 2 * x + 1 ），然后更新 ans[i - x] 为 2 * x + 1 ；最后把每个 ans[i] 用 ans[i - 1] - 2 尝试更新一下 其实以上做法也基于这个结论？ ans[i - 1] <= ans[i] + 2 ，这个可以容易地用反证法证明（类似 kmp ） 因此从 ans[(n + 1) / 2] 开始求就行了 参考代码： # pragma GCC optimize( "Ofast,no-stack-protector,unroll-loops,fast-math" ) # pragma GCC target( "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native" ) # include "bits/stdc++.h" # define mem(x) memset((x), 0, sizeof((x))) # define il __attribute__((always_inline)) using namespace std ; typedef long long ll; typedef long double ld; typedef uns
评论
发表评论