CF961F k-substrings 题解
题目链接:k-substrings
题意:
给定一个长度为 $n$ 的字符串 $S$
对于 $1 \le j \le \left\lceil\frac{n}{2}\right\rceil$ ,求 $S[k,\, n-k+1]$ 的最长且长度为奇数的 border 的长度。
输入格式:
输入的第一行是一个整数 $n(2 \le n \le 10^6)$,表示字符串的长度。
输入的第二行是一个长度为 $n$ 的字符串。
输出格式:
输出 $\lceil \frac n 2 \rceil$ 个数,其中第 $i$ 个数为 满足 $t$ 是 $i$ 子串的前缀和后缀的字符串 $t$ 的最大长度。
设 $f_i$ 为 $k=i$ 时的答案,那么显然有 $f_i \le f_{i + 1} + 2$
于是我们只需要把 $k$ 从大到小枚举并用字符串哈希计算 $f$ 即可。
时间复杂度 $\mathcal{O}(n)$
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))
char s[N];
int n, res, pw[N], hsh[N], f[N];
int gethsh(int l, int r) { return (hsh[r] + mod - hsh[l - 1] * pw[r - l + 1] % mod) % mod; }
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> (s + 1); const int m = (n - 1) / 2; pw[0] = 1;
rep(i, 1, n) pw[i] = pw[i - 1] * 89 % mod;
rep(i, 1, n) hsh[i] = (hsh[i - 1] * 89 + s[i] - 'a') % mod;
f[m + 1] = -1;
for(int i = m; ~i; i--)
{
f[i] = f[i + 1] + 2;
while(~f[i] && i * 2 + f[i] >= n) f[i] -= 2;
while(~f[i] && gethsh(i + 1, i + f[i]) != gethsh(n - i - f[i] + 1, n - i)) f[i] -= 2;
}
rep(i, 0, m) cout << f[i] << " \n"[i == m];
return 0;
}
参考文献: