제출 #1250849

#제출 시각아이디문제언어결과실행 시간메모리
1250849nhan회문 (APIO14_palindrome)C++20
100 / 100
32 ms45264 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fll; struct eertree { vector<vector<int>> t; int n, last, sz; vector<int> s, len, link, qt; eertree(int N) { t = vector<vector<int>>(N+2,vector<int>(26,0)); s = len = link = qt = vector<int>(N+2); s[0] = -1; link[0] = 1, len[0] = 0, link[1] = 1, len[1] = -1; sz = 2, last = 0, n = 1; } void add(char c) { s[n++] = c -= 'a'; while (s[n-len[last]-2] != c) last = link[last]; if (!t[last][c]) { int prev = link[last]; while (s[n-len[prev]-2] != c) prev = link[prev]; link[sz] = t[prev][c]; len[sz] = len[last]+2; t[last][c] = sz++; } qt[last = t[last][c]]++; } int size() { return sz-2; } ll propagate() { ll ret = 0; for (int i = n; i > 1; i--) { //cout<<link[i]<<'\n'; qt[link[i]] += qt[i]; ret += qt[i]; } return ret; } }; int main() { ios_base::sync_with_stdio(0);cin.tie(0); string s; cin >> s; const int n = s.size(); eertree et(n); for (char c : s) et.add(c); et.propagate(); ll ans = 0; for (int i = 0; i < n + 2; i++) { ans = max(ans, ((ll) et.qt[i]) * et.len[i]); } 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...