:::info[Description] Link. :::
:::infoSolution
结论题，但是我好像不知道结论。
一个不需要结论的做法。注意到 串可以被表示成 的形式，因此考虑 dp，设 表示确定串 为 时， 串长度最大是多少。显然此时有 ，然后直接暴力缩小 的范围即可。容易用均摊手法证明时间复杂度为 。判断是否合法使用字符串哈希即可。 :::
:::success[Code]
namespace lowspeed_song {
inline void init() {
}
char s[N];
const int base = 13331;
int h[N], bit[N], f[N];
inline int get(int l, int r) {
return (h[r] - h[l - 1] * bit[r - l + 1] % mod + mod) % mod;
}
inline void sol() {
int n, res = 0; cin >> n;
scanf("%s", s + 1);
bit[0] = 1;
for (int i = 1; i < N; ++i) bit[i] = bit[i - 1] * base % mod;
for (int i = 1; i <= n; ++i) h[i] = (h[i - 1] * base + s[i]) % mod;
for (int i = n / 2; i; --i) {
f[i] = f[i + 1] + 2;
if (f[i] + i > n / 2) f[i] = n / 2 - i;
while (f[i] && get(i + 1, i + f[i]) != get(n - i - f[i] + 1, n - i)) --f[i];
} for (int i = 1; i <= n / 2; ++i)
if (get(1, i) == get(n - i + 1, n)) res = max(res, f[i] + i);
cout << res << '\n';
}
} // namespace lowspeed_song:::
难度：蓝
鲜活指数：5
喜欢的话，留下你的评论吧～