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;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/uef83pzm