제출 #996958

#제출 시각아이디문제언어결과실행 시간메모리
996958jpfr12회문 (APIO14_palindrome)C++17
0 / 100
1062 ms6356 KiB
#include <bits/stdc++.h> typedef long long ll; typedef unsigned long long int ull; using namespace std; const int MOD = (int)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-1] != str[right-1]) return; ll val = str_hash[right] - str_hash[left-1]*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 = 1; i <= n; i++){ sol(i, i); sol(i, i+1); } ll ans = 0LL; for(auto& i: Map){ 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...