第一个点为啥WA
查看原帖
第一个点为啥WA
644963
ln001楼主2024/2/23 17:09
// Problem: 回文子串的最大长度
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/141/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define fst                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define f(x, y, z) for (register ll x = ((o_f_o || z >= y) ? (y) : ((cerr << "从" << y << "到" << z << "的循环为倒序" << endl), (y))); (o_f_o || z >= y) ? (x <= (z)) : (x >= (z)); x += ((o_f_o || z >= y) ? 1 : -1))
ll read_tmp = INT_MAX, o_f_o = 0; //read函数tmp,宏定义f只正序
inline ll read(ll &k = read_tmp);
using namespace std;

const long long INF = 0x3f3f3f3f3f3f3f3f, N = (1000000 + 10) * 2;
string s;
ll n, ans;

unsigned ll hl[N], hr[N], p[N], pr = 16341163, prr = 2909;

unsigned ll get_hash1(ll l, ll r)
{
    if (l > r)
        return 1145141919;
    return hl[r] - hl[l - 1] * p[abs(r - l) + 1];
}
unsigned ll get_hash2(ll l, ll r)
{
    if (l > r)
        return 114514191;
    return hr[l] - hr[r + 1] * p[abs(r - l) + 1];
}

void sov()
{
    ans = 0;
    for (ll i = 2 * n; i >= 2; i -= 2)
    {
        s[i] = s[i / 2];
    }
    f(i, 1, 2 * n - 1)
    {
        s[i] = 'z' + 1;
        i++;
    }
    n = s.size() - 1;

    p[0] = 1;
    f(i, 1, n)
    {
        hl[i] = hl[i - 1] * pr + s[i] - 'a' + prr;
        p[i] = p[i - 1] * pr;
    }
    f(i, n, 1) hr[i] = hr[i + 1] * pr + s[i] - 'a' + prr;
    cerr << s << endl;
    f(i, 1, n)
    {
        ll l = 1, r = min(i - 1, n - 1 - (i - 1)), mid, k = l;
        while (l <= r)
        {
            mid = l + r >> 1;
            if (get_hash1(i - mid, i - 1) == get_hash2(i + 1, i + mid))
            {
                cerr << i << "::" << mid << endl;
                k = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        cerr << i << "::" << mid << "::" << k << "::" << ans << endl;
        if (s[i] == 'z' + 1)
            ans = max(ans, k + 1);
        else
            ans = max(ans, k);
    }
    cout << ans;
}
signed main()
{
    cin >> s;
    n = s.size();
    s = " " + s + s;
    sov();
    return 0;
}
// clang-format off
inline ll read(ll&k){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}if(k!=INT_MAX)return k=x*f;return x*f;}
2024/2/23 17:09
加载中...