Submission #997237

#TimeUsernameProblemLanguageResultExecution timeMemory
997237jpfr12Palindromes (APIO14_palindrome)C++17
0 / 100
1031 ms6616 KiB
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long int ull;
using namespace std;
const ll MOD = (ll)1e9+9;
int MAXN = 1e6;
 
//classes

 
 
//global
string str;
int n;
vector<ll> str_hash;
map<ll,ll> Map;
map<ll,int> Len;
 
void computeHash(){
  ll m = 1e9+9;
  ll p = 31;
  ll pow_p = 1;
  for(int i = 1; i <= n; i++){
    str_hash[i] = (str_hash[i-1] + (str[i-1] - 'a'+1)*pow_p)%m;
    pow_p = (pow_p*p)%m;
  }
}
 
void sol(int left, int right){
  while(left >= 0 && right < n){
    if(str[left] != str[right]) return;
    ll val = str_hash[right+1] - str_hash[left]*pow(31, right-left+1);
    val = (val)%MOD;
    Map[val]++;
    Len[val] = right-left+1;
    left--;
    right++;
  }
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  //ifstream fin("longpath.in");
  //ofstream fout("longpath.out");
  //stop
  cin >> str;
  n = str.length();
  str_hash.resize(n+1);
  computeHash();
  for(int i = 0; i < n; i++){
    sol(i, i);
    sol(i, i+1);
  }
  ll ans = 0LL;
  for(auto& i: Map){
    //cout << i.first << " " << i.second << '\n';
    ans = max(ans, i.second*Len[i.first]);
  }
  cout << ans << '\n';
  return 0;
}
#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...