제출 #402692

#제출 시각아이디문제언어결과실행 시간메모리
402692BERNARB01Palindromes (APIO14_palindrome)C++17
100 / 100
28 ms35400 KiB
#include <bits/stdc++.h> using namespace std; template<const int A> class eertree { private: string s; int n, id, cr, I; vector<int> P, L, C; vector<array<int, A>> T; int par(int v) { while (I - L[v] - 2 < 0 || s[I - L[v] - 2] != s[I - 1]) { v = P[v]; } return v; } void add() { int ch = s[I++] - 'a'; cr = par(cr); if (!T[cr][ch]) { L[id] = L[cr] + 2; P[id] = T[par(P[cr])][ch]; T[cr][ch] = id++; } cr = T[cr][ch]; C[cr]++; } public: eertree(const string& _s) { s = _s; n = s.length(); id = 2; cr = I = 0; P.assign(n + 2, 0); L.assign(n + 2, 0); C.assign(n + 2, 0); T.assign(n + 2, {}); L[1] = -1; P[0] = 1; for (int i = 0; i < n; i++) { add(); } } long long solve() { for (int i = n + 1; i > 1; i--) { C[P[i]] += C[i]; } long long res = 0; for (int i = 2; i < n + 2; i++) { res = max(res, L[i] * 1LL * C[i]); } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; cout << eertree<26>(s).solve() << '\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...