不清楚为什么ce了,本地能跑
查看原帖
不清楚为什么ce了,本地能跑
1026365
LinkLoveZelda楼主2024/11/21 20:41
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1.1e7 + 10;
const int mod = 998244353, base = 131;
int n, pw[N] = {1};
string s;
struct Hash
{
    int hash[N];
    inline void init(string s, bool flag)
    {
        int n = s.size();
        s = ' ' + s;
        if (!flag)
            for (int i = 1; i <= n; i++)
                hash[i] = (1ll * hash[i - 1] * base + (s[i] - 'a')) % mod;
        else
            for (int i = n; i >= 1; i--)
                hash[i] = (1ll * hash[i + 1] * base + (s[i] - 'a')) % mod;
    }
    inline int get(int l, int r, bool flag)
    {
        if (!flag)
            return ((hash[r] - 1ll * hash[l - 1] * pw[r - l + 1]) % mod + mod) % mod;
        else
            return ((hash[l] - 1ll * hash[r + 1] * pw[r - l + 1]) % mod + mod) % mod;
    }
} H1, H2;
int max_pre[2];
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> s;
    int n = s.size();
    H1.init(s, 0);
    H2.init(s, 1);
    for (int i = 1; i <= n; i++)
        pw[i] = 1ll * pw[i - 1] * base % mod;
    int ans = 1;
    max_pre[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        int cur = i & 1, last = (i - 1) & 1;
        int len = min(i, max_pre[last] + 2);
        while (H1.get(i - len + 1, i, 0) != H2.get(i - len + 1, i, 1))
            len--;
        max_pre[cur] = len;
        ans = max(ans, max_pre[cur]);
    }
    cout << ans << endl;
    return 0;
}
2024/11/21 20:41
加载中...