제출 #721377

#제출 시각아이디문제언어결과실행 시간메모리
721377n0sk1llPalindromes (APIO14_palindrome)C++14
23 / 100
1078 ms2524 KiB
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;







//Note to self: Check for overflow

int power(int a, int n, int mod)
{
    li c=1;
    while (n)
    {
        if (n&1) (c*=a)%mod;
        a=(li)a*a%mod,n>>=1;
    }
    return c;
}

struct hesiranje
{
    int p,mod;
    int w[26];

    void setprost(int _)
    {
        p=_;
    }
    void setmod(int _)
    {
        mod=_;
    }

    int ps[10004],pi[10004];

    int pre[10004],suf[10004];

    void build(string s, int n)
    {
        mt19937 rng(time(NULL));
        ff(i,0,26) w[i]=rng()%mod;

        ps[0]=1,pi[0]=1;
        fff(i,1,n) ps[i]=(li)ps[i-1]*p%mod;
        fff(i,1,n) pi[i]=power(ps[i],mod-2,mod);

        fff(i,1,n) pre[i]=((li)pre[i-1]*p+w[s[i-1]-'a'])%mod;
        bfff(i,1,n) suf[i]=((li)suf[i+1]*p+w[s[i-1]-'a'])%mod;
    }

    int Hash(int l, int r)
    {
        return (pre[r]+mod-(li)pre[l-1]*ps[r-l+1]%mod)%mod;
    }

    int rHash(int l, int r)
    {
        return (suf[l]+mod-(li)suf[r+1]*ps[r-l+1]%mod)%mod;
    }
} h1,h2;

int main()
{
    FAST;

    string s; cin>>s;
    int n=(int)s.size();

    h1.setprost(1000003),h1.setmod(998244353);
    h2.setprost(998244353),h2.setmod(1000000007);
    h1.build(s,n),h2.build(s,n);

    li ans=0;
    fff(k,1,n)
    {
        unordered_map<li,int> kolko;
        fff(i,k,n) if (h1.Hash(i-k+1,i)==h1.rHash(i-k+1,i) && h2.Hash(i-k+1,i)==h2.rHash(i-k+1,i))
        {
            li sta=(li)h1.Hash(i-k+1,i)*(1ll<<30) + h2.Hash(i-k+1,i);
            kolko[sta]++;
        }

        for (auto it : kolko) ans=max(ans,(li)it.yy*k);
    }
    cout<<ans<<"\n";
}

//Note to self: Check for overflow

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int power(int, int, int)':
palindrome.cpp:42:24: warning: value computed is not used [-Wunused-value]
   42 |         if (n&1) (c*=a)%mod;
      |                  ~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...