Submission #762368

#	Time	Username	Problem	Language	Result	Execution time	Memory
762368		Ahmed57	Palindromes (APIO14_palindrome)	C++17	0 / 100	2 ms	2528 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
//Hashing
struct hsh{
long long a = 911382323 , mod = 972663749;
long long h[10001],p[10001];
long long 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,Hash2;
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    string s;cin>>s;
    Hash1.has(s);
    string v = s;
    reverse(v.begin(),v.end());
    Hash2.has(v);
    int sz = s.size();
    long long all = 0;
    for(long long len = 1;len<=sz;len++){
        long long ma = 0;
        unordered_map<long long,long long> mp;
        for(int i = 1;i+len-1<=sz;i++){
            int l = i , r = i+len-1;
            if(Hash1.q(l,r)==Hash2.q(sz-r+1,sz-l+1)){
                mp[Hash1.q(l,r)]++;
                ma = max(ma,mp[Hash1.q(l,r)]);
            }
        }
        all = max(ma*len,all);
    }
    cout<<all<<endl;
}

Compilation message (stderr)

palindrome.cpp: In member function 'long long int hsh::has(std::string)':
palindrome.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for(int i = 0;i<s.size();i++){
      |                   ~^~~~~~~~~
palindrome.cpp:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
   15 | }
      | ^

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