제출 #996986

#제출 시각아이디문제언어결과실행 시간메모리
996986jpfr12회문 (APIO14_palindrome)C++17
0 / 100
1056 ms6360 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 +MOD)%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...