Submission #668899

#TimeUsernameProblemLanguageResultExecution timeMemory
668899Dan4LifePalindromes (APIO14_palindrome)C++17
23 / 100
1093 ms2268 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(),a.end()
const int maxn = 1e4+10;
const int MOD = 1e9+7;

int pw[maxn], h[maxn], h2[maxn], A = 9973;
string s;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<int, int, custom_hash> M;

void comp_hash(string s, int h[])
{
    h[0] = 1;
    for(int i = 0; i < (int)s.size(); i++)
        h[i+1] = ((h[i]*A)%MOD+s[i])%MOD;
}
 
inline int get_hash(int a, int b, int h[]){
    return (h[b+1]-(h[a]*pw[b-a+1])%MOD+MOD)%MOD;
}
 
inline int mir(int ind){return (int)s.size()-ind-1;}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> s; pw[0] = 1;
    for(int i = 1; i<maxn; i++) pw[i] = (pw[i-1]*A)%MOD;
    int ans = 0, n = (int)s.size();
    comp_hash(s,h); reverse(all(s)); comp_hash(s,h2); reverse(all(s));
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            int mid = (i+j)/2;
            if(i!=j and get_hash(i,mid-(j-i+1)%2,h)
            !=get_hash(mir(j),mir(mid+1),h2)) continue;
            M[get_hash(i,j,h)]+=j-i+1;
            ans = max(ans, M[get_hash(i,j,h)]);
        }
    }
    cout << ans << "\n";
}
#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...