Submission #762397

#	Time	Username	Problem	Language	Result	Execution time	Memory
762397		Ahmed57	Palindromes (APIO14_palindrome)	C++17	23 / 100	1085 ms	7356 KiB

palindrome

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//Hashing
struct hsh{
long long a = 41 , mod = 972663749;
long long h[10001],p[10001];
void has(string s){
    h[0] = 0 , p[0] = 1;
    for(int i = 0;i<s.size();i++){
        h[i+1] = (h[i]*a+((s[i]-'a')+1))%mod;
    }
    for(int i = 1;i<=10000;i++){
        p[i] = (p[i-1]*a)%mod;
    }
}
long long q(int l,int r){return(((h[r]-h[l-1]*p[r-l+1])%mod)+mod)%mod;}
};
hsh Hash1;
vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = max(0, min(r - i, p[l + (r - i)]));
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    string s;cin>>s;
    vector<int> lol = manacher(s);
    Hash1.has(s);
    unordered_map<long long,long long,custom_hash> mp;
    long long all = 0;
    for(int i = 0;i<lol.size();i++){
        long long x = lol[i]/2;
        if(i%2==0){
            long long l = i/2 , r =i/2 , val;
            while(x--){
                val = Hash1.q(l+1,r+1);
                mp[val]++;
                all = max(all,mp[val]*(r-l+1));
                l--;r++;
            }
        }else{
            long long l = i/2 , r =i/2+1 , val;
            while(x--){
                val = Hash1.q(l+1,r+1);
                mp[val]++;
                all = max(all,mp[val]*(r-l+1));
                l--;r++;
            }
        }
    }
    cout<<all<<"\n";
}

Compilation message (stderr)

palindrome.cpp: In member function 'void hsh::has(std::string)':
palindrome.cpp:10:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i = 0;i<s.size();i++){
      |                   ~^~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0;i<lol.size();i++){
      |                   ~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27