Submission #204748

#TimeUsernameProblemLanguageResultExecution timeMemory
204748staniewzkiPalindromes (APIO14_palindrome)C++17
100 / 100
606 ms31428 KiB
#include<bits/stdc++.h> using namespace std; ostream& operator<<(ostream &out, string str) { for(char c : str) out << c; return out; } template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.first << ", " << p.second << ")"; } template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) { out << "{"; for(auto it = a.begin(); it != a.end(); it = next(it)) out << (it != a.begin() ? ", " : "") << *it; return out << "}"; } void dump() { cerr << "\n"; } template<class T, class... Ts> void dump(T a, Ts... x) { cerr << a << ", "; dump(x...); } #ifdef DEBUG # define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__) #else # define debug(...) false #endif #define REP(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define ST first #define ND second template<class T> int size(T && a) { return a.size(); } using LL = long long; using PII = pair<int, int>; struct SuffixArray { vector<int> sa, lcp, rank; SuffixArray(string& s, int lim = 256) { // lub basic_string<int> int n = size(s) + 1, k = 0, a, b; vector<int> x(s.begin(), s.end() + 1); vector<int> y(n), ws(max(n, lim)); sa = lcp = rank = y; iota(sa.begin(), sa.end(), 0); for(int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) { p = j; iota(y.begin(), y.end(), n - j); REP(i, n) if(sa[i] >= j) y[p++] = sa[i] - j; fill(ws.begin(), ws.end(), 0); REP(i, n) ws[x[i]]++; FOR(i, 1, lim - 1) ws[i] += ws[i - 1]; for(int i = n; i--;) sa[--ws[x[y[i]]]] = y[i]; swap(x, y); p = 1, x[sa[0]] = 0; FOR(i, 1, n - 1) a = sa[i - 1], b = sa[i], x[b] = (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++; } FOR(i, 1, n - 1) rank[sa[i]] = i; for(int i = 0, j; i < n - 1; lcp[rank[i++]] = k) for(k && k--, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; k++); } int operator[](int x) { return sa[x]; } }; struct RMQ { vector<vector<int>> st; vector<int> pre; RMQ(vector<int> a) { int n = size(a), lg = 0; while((1 << lg) < n) lg++; st.resize(lg + 1, vector<int>(a)); st[0] = a; FOR(i, 1, lg) REP(j, n) { st[i][j] = st[i - 1][j]; int q = j + (1 << (i - 1)); if(q < n) st[i][j] = min(st[i][j], st[i - 1][q]); } pre.resize(n + 1); FOR(i, 2, n) pre[i] = pre[i / 2] + 1; } int query(int l, int r) { int q = pre[r - l + 1], x = r - (1 << q) + 1; return min(st[q][l], st[q][x]); } }; array<vector<int>, 2> manacher(string &in) { int n = size(in); array<vector<int>, 2> radius = {{vector<int>(n - 1), vector<int>(n)}}; REP(parity, 2) { int z = parity ^ 1, L = 0, R = 0; REP(i, n - z) { int &rad = radius[parity][i]; if(i <= R - z) rad = min(R - i, radius[parity][L + (R - i - z)]); int l = i - rad + z, r = i + rad; while(0 <= l - 1 && r + 1 < n && in[l - 1] == in[r + 1]) ++rad, ++r, --l; if(r > R) L = l, R = r; } } return radius; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); string str; cin >> str; int n = size(str); SuffixArray sa(str); RMQ rmq(sa.lcp); auto get_lcp = [&](int i, int j) { if(i == j) return n - i; i = sa.rank[i], j = sa.rank[j]; if(i > j) swap(i, j); return rmq.query(i + 1, j); }; auto compare = [&](int a, int b, int i, bool equal) { int l = get_lcp(a, i); if(l >= b - a + 1) return equal; if(i + l == n) return false; return str[a + l] < str[i + l]; }; auto binsearch = [&](int a, int b, bool equal) { int l = 1, r = n + 1; while(l < r) { int mid = (l + r) / 2; if(compare(a, b, sa[mid], equal)) r = mid; else l = mid + 1; } return l; }; auto count = [&](int a, int b) -> LL { return binsearch(a, b, false) - binsearch(a, b, true); }; auto m = manacher(str); LL ans = 0; REP(p, 2) REP(i, n + p - 1) { int l = i - m[p][i] + 1 - p; int r = i + m[p][i]; if(l <= r) ans = max(ans, count(l, r) * (r - l + 1)); } cout << ans << "\n"; }
#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...